Given an expression string exp , write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in exp. For example, the program should print true for exp = “[()]{}{[()()]()}” and false for exp = “[(])”
Algorithm:
1) Declare a character stack S.
2) Now traverse the expression string exp.
a) If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[‘) then push it to stack.
b) If the current character is a closing bracket (‘)’ or ‘}’ or ‘]’) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.
3) After complete traversal, if there is some starting bracket left in stack then “not balanced”
Implementation:
C Programming:
[pastacode lang=”c” manual=”%23include%3Cstdio.h%3E%0A%23include%3Cstdlib.h%3E%0A%23define%20bool%20int%0A%20%0A%2F*%20structure%20of%20a%20stack%20node%20*%2F%0Astruct%20sNode%0A%7B%0A%20%20%20char%20data%3B%0A%20%20%20struct%20sNode%20*next%3B%0A%7D%3B%0A%20%0A%2F*%20Function%20to%20push%20an%20item%20to%20stack*%2F%0Avoid%20push(struct%20sNode**%20top_ref%2C%20int%20new_data)%3B%0A%20%0A%2F*%20Function%20to%20pop%20an%20item%20from%20stack*%2F%0Aint%20pop(struct%20sNode**%20top_ref)%3B%0A%20%0A%2F*%20Returns%201%20if%20character1%20and%20character2%20are%20matching%20left%0A%20%20%20and%20right%20Parenthesis%20*%2F%0Abool%20isMatchingPair(char%20character1%2C%20char%20character2)%0A%7B%0A%20%20%20if%20(character1%20%3D%3D%20′(‘%20%26%26%20character2%20%3D%3D%20′)’)%0A%20%20%20%20%20return%201%3B%0A%20%20%20else%20if%20(character1%20%3D%3D%20’%7B’%20%26%26%20character2%20%3D%3D%20’%7D’)%0A%20%20%20%20%20return%201%3B%0A%20%20%20else%20if%20(character1%20%3D%3D%20’%5B’%20%26%26%20character2%20%3D%3D%20’%5D’)%0A%20%20%20%20%20return%201%3B%0A%20%20%20else%0A%20%20%20%20%20return%200%3B%0A%7D%0A%20%0A%2F*Return%201%20if%20expression%20has%20balanced%20Parenthesis%20*%2F%0Abool%20areParenthesisBalanced(char%20exp%5B%5D)%0A%7B%0A%20%20%20int%20i%20%3D%200%3B%0A%20%0A%20%20%20%2F*%20Declare%20an%20empty%20character%20stack%20*%2F%0A%20%20%20struct%20sNode%20*stack%20%3D%20NULL%3B%0A%20%0A%20%20%20%2F*%20Traverse%20the%20given%20expression%20to%20check%20matching%20parenthesis%20*%2F%0A%20%20%20while%20(exp%5Bi%5D)%0A%20%20%20%7B%0A%20%20%20%20%20%20%2F*If%20the%20exp%5Bi%5D%20is%20a%20starting%20parenthesis%20then%20push%20it*%2F%0A%20%20%20%20%20%20if%20(exp%5Bi%5D%20%3D%3D%20’%7B’%20%7C%7C%20exp%5Bi%5D%20%3D%3D%20′(‘%20%7C%7C%20exp%5Bi%5D%20%3D%3D%20’%5B’)%0A%20%20%20%20%20%20%20%20push(%26stack%2C%20exp%5Bi%5D)%3B%0A%20%0A%20%20%20%20%20%20%2F*%20If%20exp%5Bi%5D%20is%20an%20ending%20parenthesis%20then%20pop%20from%20stack%20and%20%0A%20%20%20%20%20%20%20%20%20%20check%20if%20the%20popped%20parenthesis%20is%20a%20matching%20pair*%2F%0A%20%20%20%20%20%20if%20(exp%5Bi%5D%20%3D%3D%20’%7D’%20%7C%7C%20exp%5Bi%5D%20%3D%3D%20′)’%20%7C%7C%20exp%5Bi%5D%20%3D%3D%20’%5D’)%0A%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%2F*If%20we%20see%20an%20ending%20parenthesis%20without%20a%20pair%20then%20return%20false*%2F%0A%20%20%20%20%20%20%20%20%20if%20(stack%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20%20%20%20%20return%200%3B%20%0A%20%0A%20%20%20%20%20%20%20%20%20%2F*%20Pop%20the%20top%20element%20from%20stack%2C%20if%20it%20is%20not%20a%20pair%20%0A%20%20%20%20%20%20%20%20%20%20%20%20parenthesis%20of%20character%20then%20there%20is%20a%20mismatch.%0A%20%20%20%20%20%20%20%20%20%20%20%20This%20happens%20for%20expressions%20like%20%7B(%7D)%20*%2F%0A%20%20%20%20%20%20%20%20%20else%20if%20(%20!isMatchingPair(pop(%26stack)%2C%20exp%5Bi%5D)%20)%0A%20%20%20%20%20%20%20%20%20%20%20return%200%3B%0A%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20i%2B%2B%3B%0A%20%20%20%7D%0A%20%20%20%20%0A%20%20%20%2F*%20If%20there%20is%20something%20left%20in%20expression%20then%20there%20is%20a%20starting%0A%20%20%20%20%20%20parenthesis%20without%20a%20closing%20parenthesis%20*%2F%0A%20%20%20if%20(stack%20%3D%3D%20NULL)%0A%20%20%20%20%20return%201%3B%20%2F*balanced*%2F%0A%20%20%20else%0A%20%20%20%20%20return%200%3B%20%20%2F*not%20balanced*%2F%0A%7D%20%0A%20%0A%2F*%20UTILITY%20FUNCTIONS%20*%2F%0A%2F*driver%20program%20to%20test%20above%20functions*%2F%0Aint%20main()%0A%7B%0A%20%20char%20exp%5B100%5D%20%3D%20%22%7B()%7D%5B%5D%22%3B%0A%20%20if%20(areParenthesisBalanced(exp))%0A%20%20%20%20printf(%22%5Cn%20Balanced%20%22)%3B%0A%20%20else%0A%20%20%20%20printf(%22%5Cn%20Not%20Balanced%20%22)%3B%20%20%0A%20%20return%200%3B%0A%7D%20%20%20%20%0A%20%0A%2F*%20Function%20to%20push%20an%20item%20to%20stack*%2F%0Avoid%20push(struct%20sNode**%20top_ref%2C%20int%20new_data)%0A%7B%0A%20%20%2F*%20allocate%20node%20*%2F%0A%20%20struct%20sNode*%20new_node%20%3D%0A%20%20%20%20%20%20%20%20%20%20%20%20(struct%20sNode*)%20malloc(sizeof(struct%20sNode))%3B%0A%20%0A%20%20if%20(new_node%20%3D%3D%20NULL)%0A%20%20%7B%0A%20%20%20%20%20printf(%22Stack%20overflow%20%5Cn%22)%3B%0A%20%20%20%20%20getchar()%3B%0A%20%20%20%20%20exit(0)%3B%0A%20%20%7D%20%20%20%20%20%20%20%20%20%20%20%0A%20%0A%20%20%2F*%20put%20in%20the%20data%20%20*%2F%0A%20%20new_node-%3Edata%20%20%3D%20new_data%3B%0A%20%0A%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20new_node-%3Enext%20%3D%20(*top_ref)%3B%20%20%0A%20%0A%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20(*top_ref)%20%20%20%20%3D%20new_node%3B%0A%7D%0A%20%0A%2F*%20Function%20to%20pop%20an%20item%20from%20stack*%2F%0Aint%20pop(struct%20sNode**%20top_ref)%0A%7B%0A%20%20char%20res%3B%0A%20%20struct%20sNode%20*top%3B%0A%20%0A%20%20%2F*If%20stack%20is%20empty%20then%20error%20*%2F%0A%20%20if%20(*top_ref%20%3D%3D%20NULL)%0A%20%20%7B%0A%20%20%20%20%20printf(%22Stack%20overflow%20%5Cn%22)%3B%0A%20%20%20%20%20getchar()%3B%0A%20%20%20%20%20exit(0)%3B%0A%20%20%7D%0A%20%20else%0A%20%20%7B%0A%20%20%20%20%20top%20%3D%20*top_ref%3B%0A%20%20%20%20%20res%20%3D%20top-%3Edata%3B%0A%20%20%20%20%20*top_ref%20%3D%20top-%3Enext%3B%0A%20%20%20%20%20free(top)%3B%0A%20%20%20%20%20return%20res%3B%0A%20%20%7D%0A%7D” message=”” highlight=”” provider=”manual”/]Time Complexity: O(n)
Auxiliary Space: O(n) for stack.