Problems › TypeScript › patterns
Evaluate a postfix expression
A tiny expression engine accepts a calculation already written in postfix — operands first, operator after — and works it out.
- Tokens are either decimal integers or one of + - * /.
- Division is integer division, and every division in the cases is exact.
- There are never too few operands; the tokens always evaluate cleanly.
- An empty token list evaluates to zero.
evaluatePostfix(tokens: list<string>) → int
Where you start
function evaluatePostfix(tokens: string[]): number {
}Worked examples
| Call | Result |
|---|---|
evaluatePostfix(["3","4","+"]) | 7 |
evaluatePostfix(["10","3","-"]) | 7 |
evaluatePostfix(["2","3","*","4","+"]) | 10 |
evaluatePostfix(["12","4","/"]) | 3 |
Hint
One stack. Push numbers; when an operator arrives, pop two, apply it, push the result back.
Reference solution in TypeScript
function evaluatePostfix(tokens: string[]): number {
const stack: number[] = [];
for (const tok of tokens) {
if (tok.length > 1 || (tok >= '0' && tok <= '9')) {
stack.push(Number(tok));
} else {
const b = stack.pop();
const a = stack.pop();
if (tok === '+') stack.push(a + b);
else if (tok === '-') stack.push(a - b);
else if (tok === '*') stack.push(a * b);
else stack.push(Math.trunc(a / b));
}
}
return stack.length === 0 ? 0 : stack.pop();
}