Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumstack-parsing

Evaluate Reverse Polish Notation

Problem (restated)

Evaluate an arithmetic expression in reverse Polish notation. Tokens are integers or +, -, *, / (truncate toward zero).

Intuition

Postfix: push numbers; on operator pop two, apply, push result.

Approaches

Stack evaluation

Tested only

Time O(n)Space O(n)

Idea. stack of values; op(a,b) with b then a order.

Walkthrough. [“2”,“1”,“+”,“3”,“*”] → ((2+1)*3)=9.

Trade-offs. No precedence parsing needed, RPN is already ordered.

Solution

export function evalRPN(tokens: string[]): number {
  const st: number[] = [];
  for (const t of tokens) {
    if (t === "+" || t === "-" || t === "*" || t === "/") {
      const b = st.pop()!, a = st.pop()!;
      if (t === "+") st.push(a + b);
      else if (t === "-") st.push(a - b);
      else if (t === "*") st.push(a * b);
      else st.push(Math.trunc(a / b));
    } else st.push(Number(t));
  }
  return st[0]!;
}

export function evalRPN(tokens: string[]): number {
  const st: number[] = [];
  for (const t of tokens) {
    if (t === "+" || t === "-" || t === "*" || t === "/") {
      const b = st.pop()!, a = st.pop()!;
      if (t === "+") st.push(a + b);
      else if (t === "-") st.push(a - b);
      else if (t === "*") st.push(a * b);
      else st.push(Math.trunc(a / b));
    } else st.push(Number(t));
  }
  return st[0]!;
}

Template connection

Stack-parsing expression evaluation.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?