In this algorithm, we use the term \"parenthesis\" to refer to traditional paren
ID: 3709950 • 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 ) / g ]
Part 2A:
Is the expression balanced or unbalanced?
mismatch found when popping from the stackExplanation / Answer
Q. a [ b [ c - d ] * e + { f / g } ) + h
Ans: mismatch found when popping from the stack
Is the expression balanced or unbalanced?
Ans: unbalanced because of a mismatch in parentheses
Q. ( a { b + c } + [ d * e ] - f ) / g ]
Ans: closed parenthesis left on the stack
Is the expression balanced or unbalanced?
Ans: unbalanced because of an extra close parenthesis