Explain how a stack can be used to determine if an infix expression is correctly parenthesized.

What will be an ideal response?

Each time we read a ‘(‘ character, we push it on the stack. Each time we read a ‘)’ character, we perform a pop. Other characters in the expression are ignored. If, while reading the expression, we try to pop an empty stack, we halt and reject the input string. Otherwise, once we are finished reading the expression, we check to see if the stack is empty. If it is, the expression is good; otherwise it is not.