16.26. Calculator
Description
Given an arithmetic equation consisting of positive integers, +, -, * and / (no parentheses), compute the result.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
Example 1:
Input: "3+2\*2" Output: 7
Example 2:
Input: " 3/2 " Output: 1
Example 3:
Input: " 3+5 / 2 " Output: 5
Note:
- You may assume that the given expression is always valid.
- Do not use the eval built-in library function.
Solutions
Solution 1: Stack
We can use a stack to store numbers. Each time we encounter an operator, we push the number into the stack. For addition and subtraction, since their priority is the lowest, we can directly push the numbers into the stack. For multiplication and division, since their priority is higher, we need to take out the top element of the stack, perform multiplication or division with the current number, and then push the result back into the stack.
Finally, the sum of all elements in the stack is the answer.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of the string.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 |