一、基本计算器Ⅰ

题目链接

题目描述：

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

输入：s = “1 + 1”
输出：2

示例 2：

输入：s = " 2-1 + 2 "
输出：3

示例 3：

输入：s = “(1+(4+5+2)-3)+(6+8)”
输出：23

提示：

1 <= s.length <= 3 * 105
s 由数字、‘+’、‘-’、‘(’、‘)’、和 ’ ’ 组成
s 表示一个有效的表达式
‘+’ 不能用作一元运算(例如， “+1” 和 “+(2 + 3)” 无效)
‘-’ 可以用作一元运算(即 “-1” 和 “-(2 + 3)” 是有效的)
输入中不存在两个连续的操作符
每个数字和运行的计算将适合于一个有符号的 32位 整数

思路分析
用两个栈：
nums：存数字字符
ops：存符号字符

从前向后遍历字符串，因为这道题只有+/-，所以不用考虑符号优先级问题。
遍历过程有以下几种情况：

1️⃣ 空格：直接跳过
2️⃣ 数字字符：向后遍历取出完整数字，放入nums中。
3️⃣ (：直接放入ops中，等待)与之匹配
4️⃣ )：利用两个栈计算，直到遇到(，结果放入nums中，再把(出栈
5️⃣ +/-：先把前面能计算的都计算了（一直算到遇到(为止），结果放入nums中，符号放入ops中

关于首字符带符号的处理：
可以先往nums中加一个0元素，这样-就可以算进去。

关于(+和(-的处理：
每次遇到+/-的时候判断前一个字符是否是(，如果是就往nums中添加0。

关于空格的处理：
这里不能遇到空格后跳过，因为可能出现"1-( -2)"这种情况，所以先预处理字符串把空格全部消掉。

代码如下：

class Solution {
public:stack<int> nums;stack<char> ops;unordered_map<char, function<int(int, int)>> hash = {{'+', [](int x, int y){return x + y;}},{'-', [](int x, int y){return x - y;}},};void delBlack(string& s){auto it = s.find(" ");while(it != -1){s.replace(it, 1, "");it = s.find(" ");}}void calc(){if(nums.size() < 2 || ops.empty()) return;int right = nums.top();nums.pop();int left = nums.top();nums.pop();char op = ops.top();ops.pop();nums.push(hash[op](left, right));}int calculate(string s) {// 去掉空格delBlack(s);// 防止首元素为-nums.push(0);int n = s.size();for(int i = 0; i < n; i++){if(isdigit(s[i]))// 数字字符{int cur = 0, j = i;while(j < n && isdigit(s[j])){cur = cur * 10 + (s[j++] - '0');}nums.push(cur);i = j - 1;}else// 符号字符{if(s[i] == '(') ops.push(s[i]);else if(hash.count(s[i]))// + -{// "(+"情况if (i > 0 && (s[i - 1] == '(')) {nums.push(0);}// 入栈前先把前面的计算了while(ops.size() && ops.top() != '('){calc();}ops.push(s[i]);}else// ')'{// 一直算到 '('while(ops.size() && ops.top() != '('){calc();}ops.pop();}}}while(!ops.empty())calc();return nums.top();}
};

二、基本计算器Ⅱ

题目链接

题目描述：

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

输入：s = “3+2*2”
输出：7

示例 2：

输入：s = " 3/2 "
输出：1

示例 3：

输入：s = " 3+5 / 2 "
输出：5

提示：

1 <= s.length <= 3 * 105
s 由整数和算符 (‘+’, ‘-’, ‘*’, ‘/’) 组成，中间由一些空格隔开
s 表示一个 有效表达式
表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
题目数据保证答案是一个 32-bit 整数

思路分析：
这道题跟上面一道题多了一个符号优先级问题，为了解决这个问题，可以加入一个符号优先级表：

unordered_map<char,int> oper_pri = {{'+',1},{'-',1},{'*',2},{'/',2},
};

当遇到符号+ - * /的时候先判断优先级：oper_pri[ops.top()] >= oper_pri[s[i]]的时候说明可以计算前面的表达式了，先计算前面的，然后再把符号添加进ops中。

那遇到)也要计算前面的，需不需要判断优先级呢？
不需要，因为再()内部已经自动处理完了。

代码如下：

class Solution {
public:stack<int> nums;stack<char> ops;unordered_map<char, function<int(int, int)>> hash = {{'+', [](int x, int y){return x + y;}},{'-', [](int x, int y){return x - y;}},{'*', [](int x, int y){return x * y;}},{'/', [](int x, int y){return x / y;}},};unordered_map<char,int> oper_pri = {{'+',1},{'-',1},{'*',2},{'/',2},};void delBlack(string& s){auto it = s.find(" ");while(it != -1){s.replace(it, 1, "");it = s.find(" ");}}void calc(){if(nums.size() < 2 || ops.empty()) return;int right = nums.top();nums.pop();int left = nums.top();nums.pop();char op = ops.top();ops.pop();nums.push(hash[op](left, right));}int calculate(string s) {// 去掉空格delBlack(s);// 防止首元素为-nums.push(0);int n = s.size();for(int i = 0; i < n; i++){if(isdigit(s[i]))// 数字字符{int cur = 0, j = i;while(j < n && isdigit(s[j])){cur = cur * 10 + (s[j++] - '0');}nums.push(cur);i = j - 1;}else// 符号字符{if(s[i] == '(') ops.push(s[i]);else if(hash.count(s[i]))// + - * /{// "(+"情况if (i > 0 && (s[i - 1] == '(')) {nums.push(0);}// 入栈前先把前面的计算了while(ops.size() && ops.top() != '(' && oper_pri[ops.top()] >= oper_pri[s[i]]){calc();}ops.push(s[i]);}else// ')'{// 一直算到 '('while(ops.size() && ops.top() != '('){calc();}ops.pop();}}}while(!ops.empty())calc();return nums.top();}
};

---

---