Stack Expression Conversion: 29 MCQs with answers

To temporarily hold operators and parentheses

The stack is used to temporarily store operators and parentheses so that their precedence and associativity can be handled correctly during conversion.

Postfix

Postfix notation (also called Reverse Polish Notation) places the operator after its operands, e.g., AB+.

It is pushed onto the stack

An opening parenthesis is pushed onto the stack to mark a subexpression boundary; it will later be popped when the matching closing parenthesis is encountered.

True

Operands are immediately appended to the output expression; only operators and parentheses are pushed onto the stack.

Operators and left parentheses

The stack holds operators and left parentheses that are waiting to be processed.

To reorder operators based on precedence

The stack is used to reorder operators based on their precedence and associativity.

Postfix

In postfix notation, the operator appears after its operands, which is also known as Reverse Polish Notation.

Operators are popped to output until '(' is found

When a closing parenthesis is encountered, operators are popped from the stack to the output until the matching opening parenthesis is found.

Scan from left to right

The first step in the infix to postfix conversion algorithm is to scan the expression from left to right.

The direction in which operators are processed

Associativity refers to the direction in which operators of the same precedence are processed, affecting how expressions are evaluated.

A B C * +

The postfix conversion of 'A + B * C' results in 'A B C * +' as operators are placed after their operands.

To change operator precedence

Parentheses are used in infix expressions to indicate grouping and change the order of operator precedence.

Pop all remaining operators from the stack

The final step in the infix to postfix conversion process is to pop all remaining operators from the stack to the output.

A + B * C

The expression 'A + B * C' requires parentheses to indicate the correct order of operations due to operator precedence.

Operators are popped and output until an opening parenthesis is popped

A closing parenthesis triggers popping operators from the stack and appending them to the output until the matching opening parenthesis is popped (and discarded).

O(n)

Each token is processed once, and each operator is pushed and popped at most once, leading to linear time complexity O(n).

A B C * +

Multiplication has higher precedence than addition, so B*C is evaluated first, resulting in postfix: A B C * +.

A B + C *

Parentheses force addition first, so A+B is computed, then multiplied by C, giving postfix: A B + C *.

Right to left

For infix to prefix conversion, the expression is scanned from right to left to handle operator precedence correctly, and the result is reversed at the end.

+ A * B C

Multiplication has higher precedence, so B*C is grouped first, then addition: + A * B C.

* + A B C

Parentheses force addition first, then multiplication: * + A B C.

It is pushed onto the stack

In postfix to infix conversion, operands are pushed onto the stack. When an operator is encountered, two operands are popped, combined, and the result is pushed back.

(A + B) * C

The postfix expression is evaluated as A+B first, then multiplied by C, so the infix is (A + B) * C.

False

For infix to prefix conversion, the expression is scanned from right to left, and then the result is reversed to obtain the prefix expression.

Storing the final output expression

The stack is used for temporary storage of operators and parentheses; the final output is typically stored in a separate list or string, not on the stack.

The operator's precedence and associativity compared to the top of the stack

The decision is based on precedence and associativity: if the incoming operator has lower or equal precedence (and is left-associative), the top operator is popped first.

A B - C -

Subtraction is left-associative, so (A - B) - C is evaluated, giving postfix A B - C -.

A B C ^ ^

Right associativity means A ^ (B ^ C), so the postfix is A B C ^ ^.

- - A B C

Left associativity means (A - B) - C, so the prefix is - - A B C.