224.基本计算器
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。 s 由数字、’+’、’-‘、’(‘、’)’、和 ‘ ‘ 组成
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。示例 1：输入：s = “1 + 1” 输出：2
示例 2：输入：s = “ 2-1 + 2 “ 输出：3
示例 3：输入：s = “(1+(4+5+2)-3)+(6+8)” 输出：23
分析:
1.这里面关键的是记忆下来当前每一个括号之前的符号是什么, 然后用那个符号去结合数字去算加减
2.为了避免冗余的判断, 一开始先默认一个符号+, 维护一个 sign=1 表示加号, 然后扫描字符串逐个解析
3.栈维护了当前表达式经过运算后的最终的一个符号
4.如果遇到左括号, 那么需要放入当前维护的符号; 如果遇到+号, 那么当前的符号为栈顶; 如果遇到-, 那么符号要取反
5.遍历数字时顺序遍历; 遍历到末尾时根据 sign 决定计算方式
class Solution {
public:
int calculate(string s) {
int len = s.size();
int ans = 0;
int i = 0;
int sign = 1;
stack<int> ops;
ops.push(1);
while (i < len) {
if (s[i] == ' ') {
++i;
} else if (s[i] == '+') {
sign = ops.top();
++i;
} else if (s[i] == '-') {
sign = -ops.top();
++i;
} else if (s[i] == '(') {
ops.push(sign);
++i;
} else if (s[i] == ')') {
ops.pop();
++i;
} else {
long long num = 0;
while (i < len && s[i] >= '0' && s[i] <= '9') {
num = num * 10 + s[i] - '0';
++i;
}
ans += sign * num;
}
}
return ans;
}
};
227.基本计算器 II
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。示例 1：输入：s = “3+2*2” 输出：7
示例 2：输入：s = “ 3/2 “ 输出：1
示例 3：输入：s = “ 3+5 / 2 “ 输出：5
分析:
1.采用双栈思想解决这一类问题, 一个栈放数值, 一个栈放符号
2.如果符号栈顶端的优先级大于等于即将要压进去的符号优先级: 先用栈顶符号进行计算, 然后移除顶端
直到栈顶符号优先级小于要压入符号的优先级, 才把新符号压入
class Solution {
public:
int cal(int a, int b, char op) {
switch (op) {
case '+': return a+b;
case '-': return a-b;
case '*': return a*b;
case '/': return a/b;
}
return 0;
}
int calculate(string s) {
stack<int> nums;
stack<char> ops;
int i = 0;
int len = s.size();
unordered_map<char, int> priority{{'(', 0}, {')',0}, {'+',1}, {'-',1}, {'*',2}, {'/',2}};
while (i < len) {
if (s[i] == ' ') {
++i;
continue;
}
if (isdigit(s[i])) {
int start = i;
while (i + 1 < len && isdigit(s[i+1])) {
++i;
}
int num = atoi(s.substr(start, i-start+1).c_str());
nums.push(num);
} else if (s[i] == '(') {
ops.push(s[i]);
} else if (s[i] == ')') {
while (ops.top() != '(') {
char op = ops.top();
ops.pop();
int b = nums.top();
nums.pop();
int a = nums.top();
nums.pop();
int res = cal(a, b, op);
nums.push(res);
}
ops.pop();
} else {
// 这里处理+-*/运算符的优先级
while (!ops.empty() && priority[ops.top()] >= priority[s[i]]) {
char op = ops.top();
ops.pop();
int b = nums.top();
nums.pop();
int a = nums.top();
nums.pop();
int res = cal(a, b, op);
nums.push(res);
}
ops.push(s[i]);
}
++i;
}
while (ops.size() > 0) {
char op = ops.top();
ops.pop();
int b = nums.top();
nums.pop();
int a = nums.top();
nums.pop();
int res = cal(a, b, op);
nums.push(res);
}
return nums.top();
}
};
772.基本计算器 III
c实现一个基本的计算器来计算简单的表达式字符串。
表达式字符串只包含非负整数，算符 +、-、*、/ ，左括号 ( 和右括号 ) 。整数除法需要 向下截断 。
你可以假定给定的表达式总是有效的。所有的中间结果的范围均满足 [-231, 231 - 1] 。
注意：你不能使用任何将字符串作为表达式求值的内置函数，比如 eval() 。示例 1：输入：s = “1+1” 输出：2
示例 2：输入：s = “6-4/2” 输出：4
示例 3：输入：s = “2(5+52)/3+(6/2+8)” 输出：21
class Solution {
public:
int cal(int a, int b, char op) {
switch (op) {
case '+': return a+b;
case '-': return a-b;
case '*': return a*b;
case '/': return a/b;
}
return 0;
}
int calculate(string s) {
stack<int> nums;
stack<char> ops;
int i = 0;
int len = s.size();
unordered_map<char, int> priority{{'(', 0}, {')',0}, {'+',1}, {'-',1}, {'*',2}, {'/',2}};
while (i < len) {
if (s[i] == ' ') {
++i;
continue;
}
if (isdigit(s[i])) {
int start = i;
while (i + 1 < len && isdigit(s[i+1])) {
++i;
}
int num = atoi(s.substr(start, i-start+1).c_str());
nums.push(num);
} else if (s[i] == '(') {
ops.push(s[i]);
} else if (s[i] == ')') {
while (ops.top() != '(') {
char op = ops.top();
ops.pop();
int b = nums.top();
nums.pop();
int a = nums.top();
nums.pop();
int res = cal(a, b, op);
nums.push(res);
}
ops.pop();
} else {
// 这里处理+-*/运算符的优先级
while (!ops.empty() && priority[ops.top()] >= priority[s[i]]) {
char op = ops.top();
ops.pop();
int b = nums.top();
nums.pop();
int a = nums.top();
nums.pop();
int res = cal(a, b, op);
nums.push(res);
}
ops.push(s[i]);
}
++i;
}
while (ops.size() > 0) {
char op = ops.top();
ops.pop();
int b = nums.top();
nums.pop();
int a = nums.top();
nums.pop();
int res = cal(a, b, op);
nums.push(res);
}
return nums.top();
}
};
转载请注明来源, from goldandrabbit.github.io
