Given a string s which represents an expression, evaluate this expression and return its value.
The integer division should truncate toward zero.
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
Example 1:
Input: s = "3+2*2" Output: 7
Example 2:
Input: s = " 3/2 " Output: 1
Example 3:
Input: s = " 3+5 / 2 " Output: 5
Constraints:
1 <= s.length <= 3 * 105sconsists of integers and operators('+', '-', '*', '/')separated by some number of spaces.srepresents a valid expression.- All the integers in the expression are non-negative integers in the range
[0, 231 - 1]. - The answer is guaranteed to fit in a 32-bit integer.
Companies:
Facebook, Amazon, Microsoft, Roblox, Google, Apple, Snapchat, Uber
Related Topics:
Math, String, Stack
Similar Questions:
Use two stacks. One for operands nums, another for operators ops.
We push numbers into nums, and operators into ops. Before we push a new operator c into the ops, we need to eval the stacks -- calculating all the operators whose priorities are greater than or equal to the priority of c.
We also need to eval when we exhaust the input string to calculate all the operands.
In the end, nums.top() is the answer.
// OJ: https://leetcode.com/problems/basic-calculator-ii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1) becase we at most store two operators and their corresponding operands in the stacks
class Solution {
stack<int> nums;
stack<char> ops;
void eval() {
int b = nums.top(); nums.pop();
switch (ops.top()) {
case '+': nums.top() += b; break;
case '-': nums.top() -= b; break;
case '*': nums.top() *= b; break;
case '/': nums.top() /= b; break;
}
ops.pop();
}
public:
unordered_map<char, int> priority{{'+',0},{'-',0},{'*',1},{'/',1}};
int calculate(string s) {
int N = s.size();
for (int i = 0; i < N; ++i) {
if (isdigit(s[i])) {
int n = 0;
while (i < N && isdigit(s[i])) n = n * 10 + (s[i++] - '0');
--i;
nums.push(n);
} else if (s[i] != ' ') {
while (ops.size() && priority[ops.top()] >= priority[s[i]]) eval(); // Note that it's `while` here. Consider 1+2*3-4. When we see `-`, we need to `eval` twice.
ops.push(s[i]);
}
}
while (ops.size()) eval();
return nums.top();
}
};// OJ: https://leetcode.com/problems/basic-calculator-ii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
inline int priority(char op) {
if (op == '\0') return 0;
if (op == '+' || op == '-') return 1;
if (op == '*' || op == '/') return 2;
return 3;
}
vector<string> tokenize(string &s) {
vector<string> ans;
for (int i = 0, N = s.size(); i < N; ) {
while (i < N && s[i] == ' ') ++i;
if (i >= N) break;
if (isdigit(s[i])) {
int j = i;
while (i < N && isdigit(s[i])) ++i;
ans.push_back(s.substr(j, i - j));
} else ans.push_back(s.substr(i++, 1));
}
return ans;
}
void pushOps(vector<string> &ans, stack<string> &ops, string op = "") {
while (ops.size() && priority(op[0]) <= priority(ops.top()[0])) {
ans.push_back(ops.top());
ops.pop();
}
ops.push(op);
}
vector<string> toRpn(vector<string> tokens) {
vector<string> ans;
stack<string> ops;
for (auto &s : tokens) {
if (isdigit(s[0])) ans.push_back(s);
else pushOps(ans, ops, s);
}
pushOps(ans, ops);
return ans;
}
int calc(vector<string> rpn) {
stack<int> s;
int n;
for (auto &t : rpn) {
if (isdigit(t[0])) s.push(stoi(t));
else {
n = s.top();
s.pop();
switch (t[0]) {
case '+': s.top() += n; break;
case '-': s.top() -= n; break;
case '*': s.top() *= n; break;
case '/': s.top() /= n; break;
}
}
}
return s.top();
}
public:
int calculate(string s) {
return calc(toRpn(tokenize(s)));
}
};// OJ: https://leetcode.com/problems/basic-calculator-ii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
private:
int getNum(string &s, int &i) {
int ans = 0;
while (i < s.size() && isdigit(s[i])) ans = ans * 10 + (s[i++] - '0');
return ans;
}
public:
int calculate(string s) {
s.erase(remove(s.begin(), s.end(), ' '), s.end());
int i = 0, cur = getNum(s, i), prev = cur;
while (i < s.size()) {
char c = s[i++];
int n = getNum(s, i);
if (c == '+') {
cur += n;
prev = n;
} else if (c == '-') {
cur -= n;
prev = -n;
} else if (c == '*') {
cur = cur - prev + prev * n;
prev = prev * n;
} else {
cur = cur - prev + prev / n;
prev = prev / n;
}
}
return cur;
}
};// OJ: https://leetcode.com/problems/basic-calculator-ii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
int calculate(string s) {
stack<int> st;
int ans = 0, num = 0;
char op = '+';
for (int i = 0, N = s.size(); i < N; ++i) {
if (isdigit(s[i])) {
while (i < N && isdigit(s[i])) num = 10 * num + (s[i++] - '0');
--i;
}
if ((!isdigit(s[i]) && s[i] != ' ') || i == N - 1) {
if (op == '+') st.push(num);
else if (op == '-') st.push(-num);
else if (op == '*') st.top() *= num;
else if (op == '/') st.top() /= num;
op = s[i];
num = 0;
}
}
while (st.size()) {
ans += st.top();
st.pop();
}
return ans;
}
};// OJ: https://leetcode.com/problems/basic-calculator-ii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
int calculate(string s) {
int num = 0, ans = 0, cur = 0;
char op = '+';
for (int i = 0, N = s.size(); i < N; ++i) {
if (isdigit(s[i])) num = 10 * num + (s[i] - '0');
if ((!isdigit(s[i]) && s[i] != ' ') || i == N - 1) {
if (op == '+') cur += num;
else if (op == '-') cur -= num;
else if (op == '*') cur *= num;
else cur /= num;
if (s[i] == '+' || s[i] == '-' || i == N - 1) {
ans += cur;
cur = 0;
}
op = s[i];
num = 0;
}
}
return ans;
}
};