[ARRAY] Balanced Parentheses in an Expression
20 January, 2014 - 10 min read
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:
- Declare a character stack S.
- 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. - After complete traversal, if there is some starting bracket left in stack then “not balanced”
Time Complexity: O(n)
Auxiliary Space: O(n) for stack.
1: #include<stdio.h>
2: #include<stdlib.h>
3: #define bool int
4:
5: /* structure of a stack node */
6: struct sNode
7: {
8: char data;
9: struct sNode *next;
10: };
11:
12: /* Function to push an item to stack*/
13: void push(struct sNode** top_ref, int new_data);
14:
15: /* Function to pop an item from stack*/
16: int pop(struct sNode** top_ref);
17:
18: /* Returns 1 if character1 and character2 are matching left
19: and right Parenthesis */
20: bool isMatchingPair(char character1, char character2)
21: {
22: if(character1 == '(' && character2 == ')')
23: return 1;
24: else if(character1 == '{' && character2 == '}')
25: return 1;
26: else if(character1 == '[' && character2 == ']')
27: return 1;
28: else
29: return 0;
30: }
31:
32: /*Return 1 if expression has balanced Parenthesis */
33: bool areParenthesisBalanced(char exp[])
34: {
35: int i = 0;
36:
37: /* Declare an empty character stack */
38: struct sNode *stack = NULL;
39:
40: /* Traverse the given expression to check matching parenthesis */
41: while(exp[i])
42: {
43: /*If the exp[i] is a starting parenthesis then push it*/
44: if(exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
45: push(&stack, exp[i]);
46:
47: /* If exp[i] is a ending parenthesis then pop from stack and
48: check if the popped parenthesis is a matching pair*/
49: if(exp[i] == '}' || exp[i] == ')' || exp[i] == ']')
50: {
51:
52: /*If we see an ending parenthesis without a pair then return false*/
53: if(stack == NULL)
54: return 0;
55:
56: /* Pop the top element from stack, if it is not a pair
57: parenthesis of character then there is a mismatch.
58: This happens for expressions like {(}) */
59: else if ( !isMatchingPair(pop(&stack), exp[i]) )
60: return 0;
61: }
62: i++;
63: }
64:
65: /* If there is something left in expression then there is a starting
66: parenthesis without a closing parenthesis */
67: if(stack == NULL)
68: return 1; /*balanced*/
69: else
70: return 0; /*not balanced*/
71: }
72:
73: /* UTILITY FUNCTIONS */
74: /*driver program to test above functions*/
75: int main()
76: {
77: char exp[100] = "{()}[]";
78: if(areParenthesisBalanced(exp))
79: printf("\n Balanced ");
80: else
81: printf("\n Not Balanced "); \
82: getchar();
83: }
84:
85: /* Function to push an item to stack*/
86: void push(struct sNode** top_ref, int new_data)
87: {
88: /* allocate node */
89: struct sNode* new_node =
90: (struct sNode*) malloc(sizeof(struct sNode));
91:
92: if(new_node == NULL)
93: {
94: printf("Stack overflow \n");
95: getchar();
96: exit(0);
97: }
98:
99: /* put in the data */
100: new_node->data = new_data;
101:
102: /* link the old list off the new node */
103: new_node->next = (*top_ref);
104:
105: /* move the head to point to the new node */
106: (*top_ref) = new_node;
107: }
108:
109: /* Function to pop an item from stack*/
110: int pop(struct sNode** top_ref)
111: {
112: char res;
113: struct sNode *top;
114:
115: /*If stack is empty then error */
116: if(*top_ref == NULL)
117: {
118: printf("Stack overflow \n");
119: getchar();
120: exit(0);
121: }
122: else
123: {
124: top = *top_ref;
125: res = top->data;
126: *top_ref = top->next;
127: free(top);
128: return res;
129: }
130: }