Arithmetic without brackets
MediumStuck?
Show a hintHide the hint
Push numbers. On an operator, pop two values and push the result. The second value popped is the left operand.
The ideas behind this problem
Next in this lesson
The first negative number in every windowEvaluate an expression written in reverse Polish notation, where each operator comes after the two values it applies to.
The operators are +, -, * and /. Division cuts towards zero, so 7 / -2 is -3, not -4.
Worked example#
For ["2", "1", "+", "3", "*"], which means (2 + 1) * 3:
| token | action | stack afterwards |
|---|---|---|
| 2 | a number, push it | [2] |
| 1 | push it | [2, 1] |
| + | pop 1 and 2, push 2 + 1 | [3] |
| 3 | push it | [3, 3] |
| * | pop 3 and 3, push 3 * 3 | [9] |
One value is left, and that is the answer: 9.
Why a stack fits so exactly#
An operator always applies to the two most recent unused values. Not the first two, not any two: the most recent. That is precisely what a stack gives you, which is why this needs no bracket matching and no precedence rules at all. The order is already in the notation.
Order matters for the ones that are not symmetric. For - and /, the value popped second is the left operand. Pop b, then pop a, and compute a - b. Getting this backwards is the usual bug, and it passes any test using only + and *.
Constraints#
1 <= number of tokens <= 10000- Every expression is valid, and no division by zero happens
- Values fit in a signed 32 bit integer
Input
tokens is a count then that many whitespace-separated tokens.
Output
The value of the expression.
Examples
Input
5 2 1 + 3 *
Output
9
This is (2 + 1) * 3.
Input
5 4 13 5 / +
Output
6
This is 4 + (13 / 5), and 13 / 5 cuts to 2.
Input
3 7 -2 /
Output
-3
Division cuts towards zero, so this is -3 rather than -4.
Something wrong with this problem? Report an issue
Ready to try it
Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.
Free, and it stays free. No card.