Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, '+'
, '-'
, '*'
, '/'
operators, and open '('
and closing parentheses ')'
. 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 [-231, 231 - 1]
.
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval()
.
Example 1:
Input: s = "1+1" Output: 2
Example 2:
Input: s = "6-4/2" Output: 4
Example 3:
Input: s = "2*(5+5*2)/3+(6/2+8)" Output: 21
Example 4:
Input: s = "(2+6*3+5-(3*14/7+2)*5)+3" Output: -12
Example 5:
Input: s = "0" Output: 0
Constraints:
1 <= s <= 104
s
consists of digits,'+'
,'-'
,'*'
,'/'
,'('
, and')'
.s
is a valid expression.
Companies:
Amazon, Facebook, Microsoft, Uber
Related Topics:
Math, String, Stack, Recursion
Similar Questions:
- Basic Calculator (Hard)
- Basic Calculator II (Medium)
- Basic Calculator IV (Hard)
- Build Binary Expression Tree From Infix Expression (Hard)
// OJ: https://leetcode.com/problems/basic-calculator-iii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
stack<long> num;
stack<char> op;
unordered_map<char, int> priority{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
void eval() {
long b = num.top(); num.pop();
char c = op.top(); op.pop();
switch (c) {
case '+': num.top() += b; break;
case '-': num.top() -= b; break;
case '*': num.top() *= b; break;
case '/': num.top() /= b; break;
}
}
public:
int calculate(string s) {
for (int i = 0, N = s.size(); i < N; ++i) {
if (s[i] == ' ') continue;
if (isdigit(s[i])) {
long n = 0;
while (i < N && isdigit(s[i])) n = n * 10 + s[i++] - '0';
--i;
num.push(n);
} else if (s[i] == '(') op.push(s[i]);
else if (s[i] == ')') {
while (op.top() != '(') eval();
op.pop();
} else {
while (op.size() && op.top() != '(' && priority[op.top()] >= priority[s[i]]) eval();
op.push(s[i]);
}
}
while (op.size()) eval();
return num.top();
}
};