FOR FREE MATERIALS
Parenthesis checking using Stack
Back to ProgrammingDescription
Introduction:
In an expression, it offen becomes necessary to check if the parentheses (plural of parenthesis) are balanced. In such cases the expression is closely examined to check whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct. This task can be accomplished using the Stack data structure which has the property of LIFO(i.e. Last In First Out).
Procedure for Parenthesis checking using stack data structure:
Let us consider an expression [()].
exp=”[()]”.
First , we start by parsing the expression from left to right
Algorithm
Algorithm:
Input:
expression exp.
Output:
True or False.
Algo:
Step 1: Start.
Step 2: Defining the pairMatched(char1,char2) function
l If char1==’(‘ and char2==’)’ then,
(a) Return True.
l Else if char1==’{‘ and char2==’}’ then,
(a) Return True.
l Else if char1==’[‘ and char2==’]’ then,
(a) Return True.
l Else then,
(a) Return False.
Step 3: Defining the parenthesisChecking(exp) function
l Set i←0.
l Repeat substeps while i !=length(exp) then,
(a) If exp[i] in {‘(‘,’{‘,’[‘} then,
stack.push(exp[i]).
(b) Else if exp[i] in {‘}’,’)’,’]’} then,
If stack is empty then,
Return False.
Else if not pairMatched(stack.pop(),exp[i])
Return False.
(c) Set i←i+1.
l If stack is empty then,
(a) Return True.
l Else then,
(a) Return False.
Step 4: Stop.
Code
Application:
Parenthesis checking is mainly used for evaluating expressions and also by editors to validate syntax.
Complexity:
(a) Time Complexity:
In parenthesis checking using Stack, the processes that are involved are traversing the expression and pushing the starting parentheses (i.e. ‘{‘,’(‘,’[‘) into stack which requires O(n) and then popping them one by one whenever a closing parenthesis (i.e. ‘}‘,’)‘,’]‘) is found which requires O(n), thus the time complexity is O(n) where n is the length of the expression.
(b) Space Complexity:
In parenthesis checking using Stack, where the expression is of length n, the space complexity is O(n).
