This is a puzzle from LeetCode.

Solution:

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.

You may assume that the given expression is always valid.

Some examples: “3+2*2” = 7 “ 3/2 “ = 1 “ 3+5 / 2 “ = 5

Note: Do not use the eval built-in library function.

Credits: Special thanks to @ts for adding this problem and creating all test cases.

Basic Thought:

1. Parse
2. Evaluate

I make a quick but dirty solution at first:

• Parse to nigix expression
• Evaluate */ first and Evaluate +- then.

I don’t like the evaluation part. It’s urgly. A solution based on priority-map is better (assuming tokens have been parsed already):

We can optimize the solution by merging parsing and evaluating procedure. That needs us offering 2 stacks:

Let’s take a deep look inside an evaluation: `” 10+2*3+4”:

``````(calc2 " 10+2*3+4")
(calc '() '() 0 '(#\space #\1 #\0 #\+ #\2 #\* #\3 #\+ #\4)) ; 〇
(calc '() '() 0 '(#\1 #\0 #\+ #\2 #\* #\3 #\+ #\4)) ; ①
(calc '() '() 1 '(#\0 #\+ #\2 #\* #\3 #\+ #\4)) ; ②
(calc '() '() 10 '(#\+ #\2 #\* #\3 #\+ #\4)) ; ②
(calc '(#\+) '(10) #f '( #\2 #\* #\3 #\+ #\4)) ; ③
(calc '(#\+) '(10) 2 '(#\* #\3 #\+ #\4)) ; ②
(calc '(#\+ #\*) '(10 2) #f '(#\3 #\+ #\4)) ; ④
(calc '(#\+ #\*) '(10 2) 3 '(#\+ #\4)) ; ②
(calc '(#\+ #\+) '(10 6) #f '(#\4)) ; ⑤
(calc '(#\+ #\+) '(10 6) 4 '()) ; ②
(calc '(#\+ #\+) '(10 6 4) #f '() ) ; ⑥
(evaluate '(#\+ #\+) '(10 6 4)) ; ⑦
(evaluate '(#\+) '(10 10))
(evaluate '() '(20))
20
``````