Multiply before you add
Evaluate an expression with plus, minus, times and divide, where times and divide go first, by pushing terms onto a stack and merging products into the top term. About 18 minutes.
A sum of terms
Think of 3 + 2 * 2 as a sum of terms: the term 3 and the term 2 times 2. Plus and minus separate terms. Times and divide belong inside a term.
Read from the left, and remember the operator that came before the number you just finished reading. Plus pushes the number as a new term. Minus pushes its negative. Times and divide change the last term on the stack.
terms = [] terms.append(3) # + 3 terms.append(-2) # - 2 total = sum(terms) # 1
The times arrives. The saved operator is plus, so push 4. Stack: 4.
Apply when the next operator arrives
You only know a number is finished when the next operator or the end of the text arrives. So apply the saved operator then, using the number just read, and then remember the new operator.
Adding a sentinel plus at the end of the text flushes the last number with no special case. Skip spaces. At the end, add up everything on the stack. Divide rounds toward zero, which matters for negative terms.
if op == "*":
terms[-1] *= numWhat is 10 - 2 * 3?
- A4
- B24
- C16
Show the answer
4. The terms are 10 and minus 2 times 3, which is 10 minus 6.
Basic calculator with precedence
You are given a string s that is a valid expression made of non-negative integers, the operators +, -, * and /, and spaces. There are no brackets. Multiplication and division are done before addition and subtraction. Integer division truncates toward zero. Evaluate the expression and return the value. Every intermediate result fits in a 32-bit integer.
s = "3+2*2" → 7
1 ≤ length of s ≤ 100,000 · s has digits, + - * / and spaces · no division by zero