Call Stacks, Dijkstra's Shunting-Yard Algorithm & AST Evaluation

Infix Ambiguity vs. Reverse Polish Notation (Postfix)

Why is an infix expression like $3 + 4 \times 2 \uparrow 3 \uparrow 2$ ambiguous without precedence and associativity rules, whereas its Reverse Polish Notation (postfix) equivalent 3 4 2 3 2 ^ ^ * + requires zero parentheses and zero precedence rules? Because in postfix notation, every operator appears immediately after its operands, encoding the exact post-order traversal of the Abstract Syntax Tree (AST)!

Evaluating an RPN token stream is a single branch-free stack machine pass: scan tokens left to right; push numbers onto an operand stack; when a binary operator $\circ$ arrives, pop the right operand $b$, pop the left operand $a$, and push $(a \circ b)$.

Operator Precedence, Associativity & Unary Disambiguation

Visualizing AST Post-Order Equivalence & Two-Stack On-the-Fly Evaluation

Shunting-Yard Token Dispatch & Reduction Pipeline

Production Implementation: Shunting-Yard Evaluator with Unary Negation & Exponentiation

#include <cctype>
#include <cstdint>
#include <string_view>
#include <vector>

class ExpressionEvaluator {
  enum class Op : char { Add = '+', Sub = '-', Mul = '*', Div = '/', Pow = '^', Neg = '~', LParen = '(' };

  static int precedence(Op op) noexcept {
    switch (op) {
      case Op::Add: case Op::Sub: return 1;
      case Op::Mul: case Op::Div: return 2;
      case Op::Pow:               return 3;
      case Op::Neg:               return 4;
      default:                    return 0;
    }
  }

  static bool is_right_assoc(Op op) noexcept {
    return op == Op::Pow || op == Op::Neg;
  }

  static std::int64_t ipow(std::int64_t base, std::int64_t exp) noexcept {
    if (exp < 0) return 0;
    std::int64_t res = 1;
    while (exp > 0) {
      if (exp & 1) res *= base;
      base *= base;
      exp >>= 1;
    }
    return res;
  }

  static void apply_op(std::vector<std::int64_t>& vals, Op op) noexcept {
    if (op == Op::Neg) {
      vals.back() = -vals.back();
      return;
    }
    // CRITICAL: First popped is RIGHT operand, second popped is LEFT operand!
    const std::int64_t rhs = vals.back(); vals.pop_back();
    const std::int64_t lhs = vals.back(); vals.pop_back();
    switch (op) {
      case Op::Add: vals.push_back(lhs + rhs); break;
      case Op::Sub: vals.push_back(lhs - rhs); break;
      case Op::Mul: vals.push_back(lhs * rhs); break;
      case Op::Div: vals.push_back(lhs / rhs); break;
      case Op::Pow: vals.push_back(ipow(lhs, rhs)); break;
      default: break;
    }
  }

public:
  static std::int64_t evaluate(std::string_view expr) {
    std::vector<std::int64_t> vals;
    std::vector<Op> ops;
    bool expect_unary = true; // True at start, after '(', or after any operator

    for (std::size_t i = 0; i < expr.size();) {
      if (std::isspace(static_cast<unsigned char>(expr[i]))) {
        ++i;
        continue;
      }
      if (std::isdigit(static_cast<unsigned char>(expr[i]))) {
        std::int64_t num = 0;
        while (i < expr.size() && std::isdigit(static_cast<unsigned char>(expr[i]))) {
          num = num * 10 + (expr[i] - '0');
          ++i;
        }
        vals.push_back(num);
        expect_unary = false;
      } else if (expr[i] == '(') {
        ops.push_back(Op::LParen);
        expect_unary = true;
        ++i;
      } else if (expr[i] == ')') {
        while (!ops.empty() && ops.back() != Op::LParen) {
          apply_op(vals, ops.back());
          ops.pop_back();
        }
        if (!ops.empty()) ops.pop_back(); // Pop '('
        expect_unary = false;
        ++i;
      } else {
        Op cur_op = static_cast<Op>(expr[i]);
        if (cur_op == Op::Sub && expect_unary) {
          cur_op = Op::Neg;
        }
        while (!ops.empty() && ops.back() != Op::LParen) {
          const int p_top = precedence(ops.back());
          const int p_cur = precedence(cur_op);
          if (p_top > p_cur || (p_top == p_cur && !is_right_assoc(cur_op))) {
            apply_op(vals, ops.back());
            ops.pop_back();
          } else {
            break;
          }
        }
        ops.push_back(cur_op);
        expect_unary = true;
        ++i;
      }
    }

    while (!ops.empty()) {
      apply_op(vals, ops.back());
      ops.pop_back();
    }
    return vals.empty() ? 0 : vals.back();
  }
};