Implement a basic calculator to evaluate a simple expression string.

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.

## Solution: Stack

if operator is ‘+’ or ‘-’, push the current num * sign onto stack.
if operator ‘*’ or ‘/’, pop the last num from stack and * or / by the current num and push it back to stack.

The answer is the sum of numbers on stack.

3+2*2 => {3}, {3,2}, {3, 2*2} = {3, 4} => ans = 7
3 +5/2 => {3}, {3,5}, {3, 5/2} = {3, 2} => ans = 5
1 + 2*3 – 5 => {1}, {1,2}, {1,2*3} = {1,6}, {1, 6, -5} => ans = 2

Time complexity: O(n)
Space complexity: O(n)

## Related Problems

If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website

Paypal
Venmo
huahualeetcode