Basic Calculator
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.
Constraints:
- The division of two integers should truncate toward zero.
- The input does not contain any spaces other than those used to separate the integers and operators.
Examples:
Input: 3+2*2
Output: 7
Explanation: First, we calculate the multiplication 2*2 = 4. Then we add 3 + 4 = 7.
Input: 3/2
Output: 1
Explanation: The division of two integers should truncate toward zero.
Input: 3+5 / 2
Output: 5
Explanation: First, we calculate the division 5 / 2 = 2. Then we add 3 + 2 = 5.
Solutions
Stack
We iterate through the string and whenever we encounter a digit, we update the current number. Whenever we encounter an operator, we calculate the result based on the previous operator and the current number, and push the result to the stack. Finally, we sum up all the numbers in the stack to get the final result.
class Solution {
public: int calculate(string s) {
stack<int> st;
int currNum = 0;
char op = '+';
for (int i = 0;
i < s.size();
i++) {
if (s[i] == ' ') continue;
if (isdigit(s[i])) currNum = currNum * 10 + (s[i] - '0');
if (!isdigit(s[i]) || i == s.size() - 1) {
if (op == '+') st.push(currNum);
else if (op == '-') st.push(-currNum);
else if (op == '*') {
int a = st.top();
st.pop();
st.push(a * currNum);
}
else {
int a = st.top();
st.pop();
st.push(a / currNum);
}
op = s[i];
currNum = 0;
}
}
int sum = 0;
while (!st.empty()) {
sum += st.top();
st.pop();
}
return sum;
}
}
;Follow-up:
How would you handle the case where the input string contains parentheses?
