Application lab in Stacks and Expression Processing

Mission

Evaluate an integer postfix token stream.

Learning outcome: Apply a stack to postfix evaluation

Correctness contract

Invariant: Only the top element is removed, and size equals pushes minus successful pops.

Required technique: Use an operand stack and preserve left/right operand order for non-commutative operators.

Complexity target: time O(n); space O(n).

Input and output

Input: A token count n followed by exactly n integer or +, -, *, / tokens. Whitespace may be spaces or line breaks.

Output: Print the single exact numeric result with no label. Return it as a String; Main.java prints it without adding other text.

Assumptions:

• The token stream is a valid integer postfix expression with nonzero divisors.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Use an operand stack and preserve left/right operand order for non-commutative operators.
3. Trace the smallest boundary case, verify exact formatting, and justify the authored time and auxiliary-space bounds.

Implement Practice.solve(Scanner sc). Keep every provided filename and public class name unchanged.

Sample input

5 2 3 + 4 *

Sample output

20

Why the sample works: Visible walkthrough for the ordinary non-trivial path. Operands are pushed until an operator combines the two most recent values in left/right order. Input `5 2 3 + 4 *` therefore produces `20`.

Progressive hints

Try the trace and first milestone before opening a hint. Open them in order.

Hint 1 — Contract: identify what each parsed variable represents and write the invariant beside the loop or recursive method.

Hint 2 — Next step: For subtraction or division, compute secondPopped operator firstPopped.

Hint 3 — Verification: compare the structure state before and after one operation, then test the smallest valid input and a duplicate or unreachable case when allowed.