CREATE OWN LIBRARY
Checked Balanced Parenthesis using Stack
Back to ProgrammingDescription
Overview:
Stack: Stack is a linear data structure used to store a collection of data. Data is inserted using push() operation and deleted using pop() operation. Stack is a LIFO (Last in First out) data structure where data is removed from the topof the stack only.
Checking balanced parenthesis using Stack: We push the opening parenthesis onto the stack and for every closing parenthesis we pop from the stack. Finally it is checked if the stack is empty. If the stack is empty, the parenthesis is considered as balanced or else imbalanced.
Prerequisites:
- Array
- Stack
Procedure:
Consider the following parenthesis “[(){}]”. Using a stack, it is checked for balance as shown in figure below.
Algorithm
Algorithm:
Input:
1. A mathematical expression containing several paranthesises
Output:
1. Displays if all paranthesises are balanced or not
Algo:
Step 1: Start
Step 2: Set int top <= -1
Step 3: Defining push function
void push(char stack[], char ch)
Set top <=top + 1
Set stack[top] <= ch
Step 4: Defining pop function
charpop(char stack[])
Set temp <= stack[top]
Set top <= top – 1
Return temp
Step 5: Defining input function
void input(char parenthesis[])
Display “Enter expression”
Read parenthesis
Step 6: Defining checkBalancedParanthesis function
intcheckBalancedParenthesis(char parenthesis[], char stack[])
Set inti<= 0
Set char ch <= null
While (parenthesis[i]) do
Check if (parenthesis[i] = '(' OR parenthesis[i] = '{' OR parenthesis[i] = '[')
Call push(stack, parenthesis[i])
End if
Check if (top = -1)
Return 0
End if
Switch(parenthesis[i])
Case ‘)’:
Set ch<= Call pop(stack)
Check if (ch = ‘{’ OR ch = ‘[’)
Return 0
End if
Break
Case ‘}’:
Set ch<= Call pop(stack)
Check if (ch = ‘(’ OR ch = ‘[’)
Return 0
End if
Break
Case ‘]’:
Set ch<= Call pop(stack)
Check if (ch = ‘(’ OR ch = ‘{’)
Return 0
End if
Break
Set i<= i + 1
End while
Check if (top = -1)
Return 1
Else
Return 0
Step 7: Defining main function
Set char parenthesis[20] <= null
Set char *stack <= null
Set char flag <= null
Call input(parenthesis)
Set stack <= GetNode(length of parenthesis * char)
Set flag <= Call checkBalancedParenthesis(parenthesis, stack)
Check if (flag = 1)
Display “Unbalanced parenthesis”
Else
Display “Balanced parenthesis”
End if
Step 8: Stop
Code
Characteristics:
- The algorithm has linear time complexity O(n) is the length of the string storing the parenthesis.
- The algorithm uses extra space for the stack, hence, the space complexity isO(n)where n is size of the stack
- A linked list implementation of the stack can be used for dynamic stack.
Advantage:
- The algorithm has linear time complexity O(n)where n is the length of the string storing the parenthesis.
Disadvantage:
- The algorithm uses extra space for the stack, hence, the space complexity is O(n)where n is size of the stack.
- Since, the algorithm uses array implementation of the stack, memory utilization is not efficient
Complexity:
Time Complexity:
Push() operations and Pop() operations take constant time O(1). The checkBalancedParenthesis() function iterates over every parenthesis and calls the push() and pop() function. Hence, the total time complexity isO(n)+ O(1) + O(1)=O(n)where n is the length of the string storing the parentheses.
Space Complexity:
The algorithm uses extra space for the stack, hence, the space complexity is O(n)where n is size of the stack.
