算法训练营Day21|基本计算器 II
题目链接：https://leetcode.cn/problems/basic-calculator-ii/description/
优秀题解：https://leetcode.cn/problems/basic-calculator-ii/solutions/91271/chai-jie-fu-za-wen-ti-shi-xian-yi-ge-wan-zheng-ji-/
题目理解
给定一个字符串表达式
s，包含整数和运算符+、-、*、/表达式中的整数都是非负整数
计算表达式的结果
运算符优先级：乘除优先于加减
没有括号
表达式中的空格需要忽略
第一想法
思路：栈
核心思想：遇到加减法，将数字（带符号）压入栈；遇到乘除法，立即计算
遍历字符串，解析数字和运算符
用
char变量记录当前数字前的运算符遇到数字时，根据前一个运算符决定操作：
+：数字直接入栈-：数字的相反数入栈*：弹出栈顶 → 与当前数字相乘 → 结果入栈/：弹出栈顶 → 除以当前数字（向零截断）→ 结果入栈
最后将栈中所有数字相加
C++实现
class Solution { public: int calculate(string s) { stack<int> st; char sign = '+'; long long num = 0; for (int i = 0; i < s.length(); i++) { char c = s[i]; if (isdigit(c)) { num = num * 10 + (c - '0'); } if ((!isdigit(c) && c != ' ') || i == s.length() - 1) { if (sign == '+') { st.push(num); } else if (sign == '-') { st.push(-num); } else if (sign == '*') { int top = st.top(); st.pop(); st.push(top * num); } else if (sign == '/') { int top = st.top(); st.pop(); st.push(top / num); } sign = c; num = 0; } } int result = 0; while (!st.empty()) { result += st.top(); st.pop(); } return result ; } };易错提醒
忘记处理多位数字（
num = num*10 + digit）到达字符串末尾时需要处理最后一个数