Question

Consider the algorithm for determining whether a sequence of parentheses is balanced (has correct nesting). The pseudo code for this algorithm appears below.

Initialize a boolean variable validExpression to true.
while (there are more symbols in the expression){

look at the next symbol
if symbol is a {, [, or (
push it on the stack
if it is a }, ], or ){ if the stack is empty then return false
else pop the stack
}

if the element popped is not the match for symbol then return false
}
if the stack is not empty then return false, else return true.

Required:
What is the maximum number of symbols that will appear on the stack at any time for the sequence { [ ( ) ] [ ( ) ] [ ( ) ] }? why?

Answer 1

3

Step-by-step explanation:

The maximum number of symbols that will be on the stack would be 3. This is because according to the pseudocode every time that a left-facing symbol ( }, ], or ) ) it automatically ends the function or pops the last element in the stack. Therefore, the longest sequence of right-facing symbols would also equal the maximum number of symbols in the stack. In the sequence passed in the question, this would mean that the longest stack would be 3 and include the following sequence {[(