15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Scan the tokens left to right with an output list and an operator stack. Operands go straight to output. Before pushing an operator, pop every stacked operator with greater or equal precedence, stopping at an opening parenthesis. A closing parenthesis pops back to its match, and the leftovers pop at the end, in O(m) time.
| Precedence | + and - are 1, * and / are 2, all left-associative |
|---|---|
| Pop rule for an operator | pop while stack-top precedence >= incoming precedence, never past ( |
| Operand | goes straight to output |
| Time | O(m) for m tokens, each pushed and popped at most once |
| Auxiliary space | O(m) for the operator stack and output |
| Postfix evaluation | pop the right operand first, then the left |
The lesson uses three stack behaviors:
You also need the precedence order:
| Operator | Precedence | Associativity |
|---|---|---|
+, - | lower | left |
*, / | higher | left |
Left-associative means equal-precedence operators group from left to right. So:
12 + 3 + 4means:
1(2 + 3) + 4The expression 2 + (3 + 4) has different grouping.
An infix expression puts an operator between operands:
12 + 3 * 4A postfix expression puts an operator after its operands:
12 3 4 * +Postfix evaluation does not use precedence rules. The token sequence already encodes the order.
Convert this infix expression to postfix:
12 + 3 * 4Multiplication happens before addition, so postfix places 3, 4, and * before the final +:
12 3 4 * +Maintain two separate sequences:
Start with both empty:
Scan 2 + 3 * 4 left to right: operands go straight to the output, operators wait on the stack, and * is higher than + so it sits on top. Popping the stack gives 2 3 4 * +.
The operator stack is shown bottom to top. The rightmost item is the top.
Read one token at a time.
| Step | Token read | Action | Output | Operator stack, bottom → top |
|---|---|---|---|---|
| Start | — | Initialize both sequences. | [] | [] |
| 1 | 2 | It is an operand, so append it to output. | [2] | [] |
| 2 | + | The stack is empty, so push +. | [2] | [+] |
| 3 | 3 | It is an operand, so append it. | [2, 3] | [+] |
| 4 | * | * has higher precedence than stack-top +, so push *. | [2, 3] | [+, *] |
| 5 | 4 | It is an operand, so append it. | [2, 3, 4] | [+, *] |
| End | — | Pop the remaining operators, top first. | [2, 3, 4, *, +] | [] |
At step 4, keep + on the stack. The incoming * must happen earlier than +, so * stays above + and is popped first during the final drain.
The result is:
12 3 4 * +Push an opening parenthesis onto the operator stack. It acts as a boundary.
For:
1(2 + 3)the scan behaves like this:
(: push it.2: append it to output.+: push it above (.3: append it.): pop operators until ( appears.( without adding it to output.The + enters postfix output. Parentheses do not.
A closing parenthesis with no matching opening parenthesis is an error. An opening parenthesis still on the stack after the scan is also an error.
As scanning proceeds, output holds the part of postfix notation that is already safe to commit.
More precisely:
During infix-to-postfix conversion, the output contains all operands read so far and every operator whose required operands and precedence constraints are settled. The operator stack contains only operators not yet sent to output, ordered so an operator above another one must be emitted no later than the operator below it.
After reading *:
1output: [2, 3]
2operator stack: [+, *]The operands 2 and 3 are permanently placed. The * cannot yet be output because its right operand has not been read. The + cannot yet be output because multiplication must occur first.
When 4 arrives, * has both operands available in output. At the end of input, no future token can change the required order, so * is emitted before +.
Each token has one of four roles.
An operand belongs directly in postfix output.
1read operand → append to outputFor the postfix evaluator, operands are single-digit integers. The converter’s practice objective uses tokenized nonnegative integer operands.
(Push it onto the operator stack.
1read ( → push (It prevents operators below it from being popped by operators inside the parenthesized group.
)Pop operators to output until the matching opening parenthesis is on top. Then pop and discard that opening parenthesis.
1read ) → pop operators until (
2 → remove (If no opening parenthesis can be found, report an unmatched closing parenthesis.
+, -, *, or /Before pushing an incoming operator, pop each stacked operator that must occur before it.
For these left-associative operators, pop while:
1stack-top precedence >= incoming precedenceNever pop past an opening parenthesis.
Then push the incoming operator.
>= handles left associativity. Consider:
12 + 3 + 4When the second + arrives, the first + has equal precedence. Pop the first + before pushing the second:
1postfix: 2 3 + 4 +At the end of input, pop all remaining operators. If an opening parenthesis remains, report an unmatched opening parenthesis.
To evaluate postfix with single-digit integer operands:
left operator right.For:
18 2 -the first pop is 2, the right operand. The second pop is 8, the left operand:
18 - 2 = 6Reversing the pops computes 2 - 8.
1FUNCTION IsOperator(token)
2 INPUT: token
3 RETURNS: true if token is one of +, -, *, /
4 MUTATION: none
5END FUNCTION
6
7FUNCTION Precedence(operator)
8 INPUT: operator, one of +, -, *, /
9 RETURNS: 1 for + or -; 2 for * or /
10 PRECONDITION: operator is valid
11 MUTATION: none
12END FUNCTION
13
14FUNCTION Apply(leftOperand, operator, rightOperand)
15 INPUT: two integer operands and one of +, -, *, /
16 RETURNS: leftOperand operator rightOperand
17 PRECONDITION: division, if used, must have a valid nonzero right operand
18 MUTATION: none
19END FUNCTION1FUNCTION HasBalancedParentheses(tokens)
2 INPUT: tokens, a sequence that may contain ( and )
3 RETURNS: true when every closing parenthesis matches an earlier opening
4 parenthesis and no opening parenthesis remains
5 MUTATION: does not modify tokens
6
7 CREATE empty stack parentheses
8
9 FOR EACH token IN tokens
10 IF token = "("
11 PUSH token onto parentheses
12 ELSE IF token = ")"
13 IF parentheses is empty
14 RETURN false
15 END IF
16 POP parentheses
17 END IF
18 END FOR
19
20 RETURN parentheses is empty
21END FUNCTION1FUNCTION InfixToPostfix(tokens)
2 INPUT: tokens containing nonnegative integer operands, +, -, *, /, (, and )
3 RETURNS: a sequence of postfix tokens,
4 or reports unmatched parentheses
5 MUTATION: does not modify tokens
6
7 CREATE empty sequence output
8 CREATE empty stack operators
9
10 FOR EACH token IN tokens
11 IF token is an operand
12 APPEND token to output
13
14 ELSE IF token = "("
15 PUSH token onto operators
16
17 ELSE IF token = ")"
18 WHILE operators is not empty AND PEEK operators ≠ "("
19 APPEND POP operators to output
20 END WHILE
21
22 IF operators is empty
23 REPORT "unmatched closing parenthesis"
24 END IF
25
26 POP operators // discard the matching "("
27
28 ELSE IF IsOperator(token)
29 WHILE operators is not empty
30 AND PEEK operators ≠ "("
31 AND Precedence(PEEK operators) >= Precedence(token)
32 APPEND POP operators to output
33 END WHILE
34
35 PUSH token onto operators
36 END IF
37 END FOR
38
39 WHILE operators is not empty
40 IF PEEK operators = "("
41 REPORT "unmatched opening parenthesis"
42 END IF
43 APPEND POP operators to output
44 END WHILE
45
46 RETURN output
47END FUNCTION1FUNCTION EvaluatePostfix(tokens)
2 INPUT: postfix tokens with single-digit integer operands and +, -, *, /
3 RETURNS: the integer expression value
4 MUTATION: does not modify tokens
5
6 CREATE empty stack values
7
8 FOR EACH token IN tokens
9 IF token is a single-digit integer operand
10 PUSH integer value of token onto values
11
12 ELSE IF IsOperator(token)
13 rightOperand ← POP values
14 leftOperand ← POP values
15 result ← Apply(leftOperand, token, rightOperand)
16 PUSH result onto values
17 END IF
18 END FOR
19
20 RETURN POP values
21END FUNCTIONUse the original token sequence:
1[2, +, 3, *, 4]Run InfixToPostfix(tokens).
| Pseudocode action | Token / condition | Output after action | Operator stack after action |
|---|---|---|---|
Create output | — | [] | — |
Create operators | — | [] | [] |
FOR EACH token | 2 | [] | [] |
IF token is an operand | true | — | — |
APPEND token to output | append 2 | [2] | [] |
FOR EACH token | + | [2] | [] |
ELSE IF IsOperator(token) | true | — | — |
Operator WHILE condition | stack empty, so false | [2] | [] |
PUSH token onto operators | push + | [2] | [+] |
FOR EACH token | 3 | [2] | [+] |
IF token is an operand | true | — | — |
APPEND token to output | append 3 | [2, 3] | [+] |
FOR EACH token | * | [2, 3] | [+] |
ELSE IF IsOperator(token) | true | — | — |
Operator WHILE condition | Precedence(+) >= Precedence(*) is 1 >= 2, false | [2, 3] | [+] |
PUSH token onto operators | push * | [2, 3] | [+, *] |
FOR EACH token | 4 | [2, 3] | [+, *] |
IF token is an operand | true | — | — |
APPEND token to output | append 4 | [2, 3, 4] | [+, *] |
Final WHILE | stack not empty; top is * | [2, 3, 4] | [+, *] |
APPEND POP operators | pop * | [2, 3, 4, *] | [+] |
Final WHILE | stack not empty; top is + | [2, 3, 4, *] | [+] |
APPEND POP operators | pop + | [2, 3, 4, *, +] | [] |
Final WHILE | stack empty, stop | [2, 3, 4, *, +] | [] |
RETURN output | — | [2, 3, 4, *, +] | [] |
The postfix expression is:
12 3 4 * +We prove that InfixToPostfix returns postfix tokens with the required operand order, precedence order, and parenthesis behavior.
Before the scan begins:
1output = []
2operators = []No operands or operators have been read. Output correctly contains all settled tokens read so far: none. The operator stack contains no unread-output operators. The stated invariant holds.
Assume the invariant holds before processing the next token.
If the token is an operand, the algorithm appends it once to output. The placement is valid because operands appear in postfix before an operator that uses them. No stack order changes.
If the token is (, the algorithm pushes it. It creates a boundary. Operators below it cannot be popped by an operator inside the group because the operator-pop loop stops when it sees (.
If the token is ), the algorithm pops all operators above the matching (. Those operators belong inside the parenthesized group and have already had their operands read. The matching ( is removed without entering output. If no matching opening parenthesis exists, the algorithm reports an unmatched closing parenthesis instead of producing an invalid conversion.
If the token is an operator, the algorithm pops every stacked operator with precedence greater than or equal to the incoming operator, stopping at ( or at a lower-precedence operator. A greater-precedence operator must be performed first. An equal-precedence operator must be emitted first because +, -, *, and / are left-associative. The incoming operator is then pushed and remains waiting for later operands or later ordering decisions.
In every case, each read operand is in output exactly once. Operators enter output only after their operands are available and when precedence and parenthesis constraints permit it. The invariant is preserved.
After all tokens are scanned, no unread operands remain. The final loop pops the remaining operators from top to bottom.
By the invariant, an operator above another must be emitted no later than the one below it. The final drain preserves the required order.
If ( remains, the expression has an unmatched opening parenthesis, and the algorithm reports it. Otherwise, every operand appears exactly once, every operator appears after its operands, and precedence and left associativity have been enforced. The returned sequence is valid postfix notation for the input expression.
For an operator in postfix notation, the most recently pushed value is its right operand. The value below it is its left operand.
The evaluator performs:
1rightOperand ← POP values
2leftOperand ← POP values
3Apply(leftOperand, operator, rightOperand)Subtraction and division use the required order:
1leftOperand operator rightOperandFor 8 2 -, the evaluator computes 8 - 2.
Let m be the number of tokens.
The outer scan reads each of the m tokens once.
An operator can be:
An opening parenthesis also enters the stack at most once and leaves it at most once.
The nested WHILE loops do not repeatedly pop the same item. Across the full conversion, there are at most O(m) pushes and O(m) pops, including the final drain.
1time: O(m)The output can hold O(m) tokens. The operator stack can also hold O(m) tokens, such as many opening parentheses or operators waiting to be emitted.
1auxiliary space: O(m)The evaluator reads each postfix token once.
The total stack work is proportional to the number of tokens:
1time: O(m)In the worst case, the value stack can hold O(m) values before enough operators appear to reduce it:
1auxiliary stack space: O(m)Incorrect assumption: Push every operator immediately and leave the stack order unresolved.
Exposing input:
12 + 3 * 4Wrong postfix:
12 3 + 4 *The output evaluates (2 + 3) * 4, which changes the meaning.
Correction: When * arrives above +, keep * above + because * has higher precedence. The final stack drain emits:
12 3 4 * +Incorrect line: Pop only operators with strictly greater precedence.
1WHILE Precedence(PEEK operators) > Precedence(token)Exposing input:
12 + 3 + 4The first + stays on the stack when the second + arrives.
Wrong postfix:
12 3 4 + +That groups the expression from the right:
12 + (3 + 4)Correction: For left-associative operators, pop equal precedence too:
1WHILE Precedence(PEEK operators) >= Precedence(token)The correct postfix form is:
12 3 + 4 +Incorrect action: Append ( to postfix output.
Exposing input:
1(2 + 3)Wrong output: It contains a parenthesis token, such as:
12 3 + (Parentheses are control markers during conversion. They are not postfix operators.
Correction: When ) is read, pop operators up to (, then pop and discard the ( itself.
Incorrect assumption: Every closing parenthesis will find an opening parenthesis, and no opening parenthesis remains at the end.
Exposing input:
12 + )3(At ), the operator stack has no matching (.
Correction: If the stack becomes empty before finding (, report an unmatched closing parenthesis.
A different exposing input is:
1(2 + 3After scanning all tokens, ( remains on the stack.
Correction: During the final drain, report an unmatched opening parenthesis instead of outputting (.
Incorrect lines:
1leftOperand ← POP values
2rightOperand ← POP values
3result ← Apply(leftOperand, token, rightOperand)Exposing input:
18 2 -The first pop is 2, but the incorrect code calls it the left operand. It computes:
12 - 8 = -6Correction: Pop the right operand first, then the left operand:
1rightOperand ← POP values
2leftOperand ← POP valuesThen compute:
18 - 2 = 6| Input | Required result |
|---|---|
8 | Postfix output: 8 |
2 + 3 + 4 | Postfix output: 2 3 + 4 + |
(2 + 3) * 4 | Postfix output: 2 3 + 4 * |
2 * (3 + 4) | Postfix output: 2 3 4 + * |
(2 + 3 | Report unmatched opening parenthesis |
2 + )3( | Report unmatched closing parenthesis |
8 2 - | Evaluate to 6, not -6 |
Implement conversion of tokenized infix expressions containing nonnegative integer operands, +, -, *, /, and parentheses into space-separated postfix.
Your tests must cover this contract:
+, -, *, and / are left-associative, so equal-precedence stacked operators are popped first;1PREC = {"+": 1, "-": 1, "*": 2, "/": 2}
2
3def infix_to_postfix(tokens):
4 output, operators = [], []
5 for token in tokens:
6 if token.isdigit():
7 output.append(token)
8 elif token == "(":
9 operators.append(token)
10 elif token == ")":
11 while operators and operators[-1] != "(":
12 output.append(operators.pop())
13 if not operators:
14 raise ValueError("unmatched closing parenthesis")
15 operators.pop() # discard the "("
16 else:
17 # >= because the operators are left-associative
18 while operators and operators[-1] != "(" and PREC[operators[-1]] >= PREC[token]:
19 output.append(operators.pop())
20 operators.append(token)
21 while operators:
22 if operators[-1] == "(":
23 raise ValueError("unmatched opening parenthesis")
24 output.append(operators.pop())
25 return output
26
27def evaluate_postfix(tokens):
28 values = []
29 for token in tokens:
30 if token.isdigit():
31 values.append(int(token))
32 else:
33 right = values.pop() # right operand comes off first
34 left = values.pop()
35 if token == "+":
36 values.append(left + right)
37 elif token == "-":
38 values.append(left - right)
39 elif token == "*":
40 values.append(left * right)
41 else:
42 values.append(left // right)
43 return values.pop()
44
45for expr in ["2 + 3 * 4", "2 + 3 + 4", "( 2 + 3 ) * 4", "2 * ( 3 + 4 )"]:
46 post = infix_to_postfix(expr.split())
47 print(expr, "->", " ".join(post), "=", evaluate_postfix(post))
48print("8 2 - =", evaluate_postfix("8 2 -".split()))
49for expr in ["( 2 + 3", "2 + ) 3 ("]:
50 try:
51 infix_to_postfix(expr.split())
52 except ValueError as e:
53 print(expr, "-> error:", e)1import java.util.ArrayDeque;
2import java.util.ArrayList;
3import java.util.Deque;
4import java.util.List;
5
6public class Main {
7 static int prec(String op) {
8 return (op.equals("+") || op.equals("-")) ? 1 : 2;
9 }
10
11 static boolean isOperand(String t) {
12 return Character.isDigit(t.charAt(0));
13 }
14
15 static List<String> infixToPostfix(String[] tokens) {
16 List<String> output = new ArrayList<>();
17 Deque<String> operators = new ArrayDeque<>();
18 for (String token : tokens) {
19 if (isOperand(token)) {
20 output.add(token);
21 } else if (token.equals("(")) {
22 operators.push(token);
23 } else if (token.equals(")")) {
24 while (!operators.isEmpty() && !operators.peek().equals("(")) output.add(operators.pop());
25 if (operators.isEmpty()) throw new IllegalArgumentException("unmatched closing parenthesis");
26 operators.pop(); // discard the "("
27 } else {
28 // >= because the operators are left-associative
29 while (!operators.isEmpty() && !operators.peek().equals("(")
30 && prec(operators.peek()) >= prec(token)) {
31 output.add(operators.pop());
32 }
33 operators.push(token);
34 }
35 }
36 while (!operators.isEmpty()) {
37 if (operators.peek().equals("(")) throw new IllegalArgumentException("unmatched opening parenthesis");
38 output.add(operators.pop());
39 }
40 return output;
41 }
42
43 static int evaluatePostfix(List<String> tokens) {
44 Deque<Integer> values = new ArrayDeque<>();
45 for (String token : tokens) {
46 if (isOperand(token)) {
47 values.push(Integer.parseInt(token));
48 } else {
49 int right = values.pop(); // right operand comes off first
50 int left = values.pop();
51 switch (token) {
52 case "+": values.push(left + right); break;
53 case "-": values.push(left - right); break;
54 case "*": values.push(left * right); break;
55 default: values.push(left / right);
56 }
57 }
58 }
59 return values.pop();
60 }
61
62 public static void main(String[] args) {
63 String[] exprs = {"2 + 3 * 4", "2 + 3 + 4", "( 2 + 3 ) * 4", "2 * ( 3 + 4 )"};
64 for (String expr : exprs) {
65 List<String> post = infixToPostfix(expr.split(" "));
66 System.out.println(expr + " -> " + String.join(" ", post) + " = " + evaluatePostfix(post));
67 }
68 System.out.println("8 2 - = " + evaluatePostfix(List.of("8", "2", "-")));
69 for (String expr : new String[]{"( 2 + 3", "2 + ) 3 ("}) {
70 try {
71 infixToPostfix(expr.split(" "));
72 } catch (IllegalArgumentException e) {
73 System.out.println(expr + " -> error: " + e.getMessage());
74 }
75 }
76 }
77}1#include <cctype>
2#include <iostream>
3#include <sstream>
4#include <stack>
5#include <stdexcept>
6#include <string>
7#include <vector>
8using namespace std;
9
10int prec(const string& op) { return (op == "+" || op == "-") ? 1 : 2; }
11
12bool isOperand(const string& t) { return isdigit((unsigned char)t[0]); }
13
14vector<string> split(const string& s) {
15 istringstream in(s);
16 vector<string> out;
17 string t;
18 while (in >> t) out.push_back(t);
19 return out;
20}
21
22string join(const vector<string>& v) {
23 string out;
24 for (size_t i = 0; i < v.size(); i++) out += (i ? " " : "") + v[i];
25 return out;
26}
27
28vector<string> infixToPostfix(const vector<string>& tokens) {
29 vector<string> output;
30 stack<string> operators;
31 for (const string& token : tokens) {
32 if (isOperand(token)) {
33 output.push_back(token);
34 } else if (token == "(") {
35 operators.push(token);
36 } else if (token == ")") {
37 while (!operators.empty() && operators.top() != "(") {
38 output.push_back(operators.top());
39 operators.pop();
40 }
41 if (operators.empty()) throw runtime_error("unmatched closing parenthesis");
42 operators.pop(); // discard the "("
43 } else {
44 // >= because the operators are left-associative
45 while (!operators.empty() && operators.top() != "(" && prec(operators.top()) >= prec(token)) {
46 output.push_back(operators.top());
47 operators.pop();
48 }
49 operators.push(token);
50 }
51 }
52 while (!operators.empty()) {
53 if (operators.top() == "(") throw runtime_error("unmatched opening parenthesis");
54 output.push_back(operators.top());
55 operators.pop();
56 }
57 return output;
58}
59
60int evaluatePostfix(const vector<string>& tokens) {
61 stack<int> values;
62 for (const string& token : tokens) {
63 if (isOperand(token)) {
64 values.push(stoi(token));
65 } else {
66 int right = values.top(); values.pop(); // right operand comes off first
67 int left = values.top(); values.pop();
68 if (token == "+") values.push(left + right);
69 else if (token == "-") values.push(left - right);
70 else if (token == "*") values.push(left * right);
71 else values.push(left / right);
72 }
73 }
74 return values.top();
75}
76
77int main() {
78 for (string expr : {"2 + 3 * 4", "2 + 3 + 4", "( 2 + 3 ) * 4", "2 * ( 3 + 4 )"}) {
79 vector<string> post = infixToPostfix(split(expr));
80 cout << expr << " -> " << join(post) << " = " << evaluatePostfix(post) << endl;
81 }
82 cout << "8 2 - = " << evaluatePostfix(split("8 2 -")) << endl;
83 for (string expr : {"( 2 + 3", "2 + ) 3 ("}) {
84 try {
85 infixToPostfix(split(expr));
86 } catch (const runtime_error& e) {
87 cout << expr << " -> error: " << e.what() << endl;
88 }
89 }
90}1const PREC = { '+': 1, '-': 1, '*': 2, '/': 2 };
2const isOperand = (t) => /^\d+$/.test(t);
3
4function infixToPostfix(tokens) {
5 const output = [];
6 const operators = [];
7 for (const token of tokens) {
8 if (isOperand(token)) {
9 output.push(token);
10 } else if (token === '(') {
11 operators.push(token);
12 } else if (token === ')') {
13 while (operators.length && operators[operators.length - 1] !== '(') output.push(operators.pop());
14 if (!operators.length) throw new Error('unmatched closing parenthesis');
15 operators.pop(); // discard the "("
16 } else {
17 // >= because the operators are left-associative
18 while (operators.length && operators[operators.length - 1] !== '('
19 && PREC[operators[operators.length - 1]] >= PREC[token]) {
20 output.push(operators.pop());
21 }
22 operators.push(token);
23 }
24 }
25 while (operators.length) {
26 if (operators[operators.length - 1] === '(') throw new Error('unmatched opening parenthesis');
27 output.push(operators.pop());
28 }
29 return output;
30}
31
32function evaluatePostfix(tokens) {
33 const values = [];
34 for (const token of tokens) {
35 if (isOperand(token)) {
36 values.push(Number(token));
37 } else {
38 const right = values.pop(); // right operand comes off first
39 const left = values.pop();
40 if (token === '+') values.push(left + right);
41 else if (token === '-') values.push(left - right);
42 else if (token === '*') values.push(left * right);
43 else values.push(Math.trunc(left / right));
44 }
45 }
46 return values.pop();
47}
48
49for (const expr of ['2 + 3 * 4', '2 + 3 + 4', '( 2 + 3 ) * 4', '2 * ( 3 + 4 )']) {
50 const post = infixToPostfix(expr.split(' '));
51 console.log(`${expr} -> ${post.join(' ')} = ${evaluatePostfix(post)}`);
52}
53console.log(`8 2 - = ${evaluatePostfix('8 2 -'.split(' '))}`);
54for (const expr of ['( 2 + 3', '2 + ) 3 (']) {
55 try {
56 infixToPostfix(expr.split(' '));
57 } catch (e) {
58 console.log(`${expr} -> error: ${e.message}`);
59 }
60}Scan left to right with a value stack. Push each operand. On an operator, pop the right operand, pop the left operand, compute left operator right and push the result. For 2 3 4 * +, 3 * 4 gives 12, then 2 + 12 gives 14.
The operators are left-associative, so an equal-precedence operator already on the stack must go first. With strict >, the input 2 + 3 + 4 yields 2 3 4 + +, which groups as 2 + (3 + 4).
They never reach the output. An opening parenthesis is pushed as a boundary that blocks popping. A closing parenthesis pops operators to output until it meets the opening one, then discards it.
The token order already fixes the evaluation order. In 2 3 4 * +, the * sits right after its operands 3 and 4, so it runs before the +.
The most recently pushed value is the right operand. For 8 2 -, the first pop gives 2 and the second gives 8, so the result is 8 - 2 = 6. Swapping the pops computes 2 - 8.