Description
Given a string s which represents an expression, evaluate this expression and return its value.
The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of $[-2^{31}, 2^{31} - 1]$.
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
Solution
Consider in solving a mathematical expression, we need to process multiplication and division before addition and subtraction. Therefore, we could use a stack and first process all the multiplications and divisions and push the results back into the stack. Then we calculate addition and subtraction to get the result.
However, I found an ingenuous way of doing this with a stringstream. Couldn’t find the original author of this piece of code as I dig this up from an submission I did a few years ago.
- We process the whole expression from the start and record the last value we processed. If we encounter an multiplication or division operator, we would revert the addition / subtraction done in the last operation.
- Do the multiplication and division, then add back the last added / subtracted number.
Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int calculate(std::string s) {
char op;
std::stringstream ss("+" + s); // init stringstream with arithmithic expression
// starts with a + operator to initialize result
// to the first number in the expression
int result = 0, last, rhs;
while (ss >> op >> rhs) {
if (op == '+' || op == '-') {
rhs = (op == '+')? rhs: -rhs;
result += rhs;
}
else {
rhs = (op == '*')? last * rhs: last / rhs;
result = result - last + rhs;
}
last = rhs;
}
return result;
}
};