In this algorithm, we use the term \"parenthesis\" to refer to traditional paren
ID: 3709955 • Letter: I
Question
In this algorithm, we use the term "parenthesis" to refer to traditional parentheses () but also curly brackets {} or other styles of brackets [].
When checking for balanced parentheses, we first remove all values and operators, leaving just the parentheses. Then there are four cases we need to look for:
balanced
example: { ( ) }
unbalanced- extra open parenthesis
example: { ( )
unbalanced- extra closed parenthesis
example: ( ) }
unbalanced- mismatched (cross-over) parentheses
example: { ( } )
Algorithm
The basic idea is to gather up open parentheses on the stack. When we find a close parenthesis, we pop the top element of the stack. The two parentheses should match. When we are done, the stack should be empty.
Here is the pseudocode:
while there are more tokens, read in a token
if the token is an open parenthesis
push the token onto the stack
else (the token is a closed parenthesis)
if the stack is empty
the expression is unbalanced (we're done- return false because of extra closed parentheses)
else (the stack is not empty)
pop a token
if the closed and open parenthesis don't match
the expression is unbalanced (we're done- return false because of mismatched parentheses)
// there are no more tokens left- the while loop is done
if the stack is empty
the expression is balanced (we're done- return true)
else (the stack has tokens remaining in it)
the expression is unbalanced (we're done- return false because of extra open parentheses)
Question: evaluate whether the 2 parentheses are balanced. Select the situation that will cause the algorithm to end.
a [ b [ c - d ] * e + { f / g } ) + h
empty stack and no more tokens
Part 2A:
Is the expression balanced or unbalanced?
unbalanced because of an extra open parenthesis
a * ( b / { c + ( d - e ) } * f )
closed parenthesis left on the stack
Part 2A:
Is the expression balanced or unbalanced?
mismatch found when popping from the stackExplanation / Answer
Question :-
a [ b [ c - d ] * e + { f / g } ) + h
empty stack and no more tokens
Solution:-
for a [ b [ c - d ] * e + { f / g } ) + h expression :-
the parenthesis after removal of characters and expressions will be:-
[ [ ] { } )
Scan this expression :-
input bracket '['
Step1 )Stack push element = '[' (Stack CONTENT = '[' )
input bracket '['
Step 2) stack push element = '[' (Stack CONTENT = '[ [' )
input bracket ']'
Step 3) stack pop element = ']' ( pop from stack and compare with this if match pop and continue) (Stack CONTENT = '[' )
input bracket '{'
Step 4) stack PUSH element = '{' (Stack CONTENT = '[{' )
input bracket '}'
Step 5) stack pop element= '}' (pop from stack and compare with this if match pop and continue) (Stack CONTENT = '[' )
input bracket ')'
Step 5) stack pop element = ')' ( pop from stack and compare with this if match pop and continue ELSE BREAK) (Stack CONTENT = '[' )
There is a mismatch in the bracket poped from stack and its not a valid expression.
So correct answer for this will be mismatch found when popping from the stack.
Question : -
Part 2A:
Is the expression balanced or unbalanced?
unbalanced because of an extra open parenthesis
Answer for this will be unbalanced because of a mismatch in parentheses ( as explained above )
Question :-
a * ( b / { c + ( d - e ) } * f )
closed parenthesis left on the stack
Solution:-
input expression is :- a * ( b / { c + ( d - e ) } * f )
input expression after removing operator and opearnts is :- ( { ( ) } )
Scan this expression :-
input bracket '('
Step1 )Stack push element = '(' ( Stack CONTENT = ( )
input bracket '{'
Step 2) stack push element = '{' (Stack CONTENT = ( { )
input bracket '('
Step 3) stack push element = '(' ( Stack CONTENT = ({( )
input bracket ')'
Step 4) stack POP element = ')' (POP from stack and match the parenthesis if match pop and continue) ( Stack CONTENT = ({ )
input bracket '}'
Step 5) stack pop element= '}' (pop from stack and compare with this if match pop and continue) ( Stack CONTENT = ( )
input bracket ')'
Step 6) stack pop element = ')' ( pop from stack and compare with this if match pop and continue ELSE BREAK) (Stack CONTENT = EMPTY )
Finally everything got a match and stack is empty so its a valid expression where all the parenthesis got a match.
So the answer for this question will be :-
empty stack and no more tokens
Question :-
Part 2A:
Is the expression balanced or unbalanced?
unbalanced because of an extra open parenthesis
Answer :- balanced ( as we saw above the expression is valid and balanced one).
mismatch found when popping from the stack