[Leetcode] 227.基本计算器
标题：[Leetcode] 227.基本计算器
个人主页：@水墨不写bug
（图片来源于网络）
// _ooOoo_ //
// o8888888o //
// 88" . "88 //
// (| ^_^ |) //
// O\ = /O //
// ____/`---'\____ //
// .' \\| |// `. //
// / \\||| : |||// \ //
// / _||||| -:- |||||- \ //
// | | \\\ - /// | | //
// | \_| ''\---/'' | | //
// \ .-\__ `-` ___/-. / //
// ___`. .' /--.--\ `. . ___ //
// ."" '< `.___\_<|>_/___.' >'"". //
// | | : `- \`.;`\ _ /`;.`/ - ` : | | //
// \ \ `-. \_ __\ /__ _/ .-` / / //
// ========`-.____`-.___\_____/___.-`____.-'======== //
// `=---=' //
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ //
// 佛祖保佑 永无BUG 永不修改 //
目录
一、[Leetcode] 227.基本计算器（点击进入题目）
算法操作：
算法原理：
总结：
正文开始：
计算器你一定用过， 但是我们用的计算器一般是及时输入输出型的，我们输入一个计算表达式，然后计算器输出一个值代表结果。但是如果这个表达式存储在字符串结构中，又该如何计算结果呢？这就是本篇Leetcode题目分享的题目背景。
一、[Leetcode] 227.基本计算器（点击进入题目）
给你一个字符串表达式
s，请你实现一个基本计算器来计算并返回它的值。整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在
[-2^31, 2^31 - 1]的范围内。注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如
eval()。示例 1：
输入：s = "3+2*2" 输出：7示例 2：
输入：s = " 3/2 " 输出：1示例 3：
输入：s = " 3+5 / 2 " 输出：5提示：
1 <= s.length <= 3 * 10^5s由整数和算符('+', '-', '*', '/')组成，中间由一些空格隔开s表示一个 有效表达式- 表达式中的所有整数都是非负整数，且在范围
[0, 2^31 - 1]内- 题目数据保证答案是一个 32-bit 整数
这一类题目是属于表达式求值的问题，这一类问题的通用解决方法就是使用栈来模拟这个过程。
具体来说，我们需要两个栈，一个存储数字，另一个存储运算符。但是本题比较特别，题目要求中说明：表达式串中不含括号，所以这就会引出本题的优化解法：用一个栈和一个变量解决本题。
那么如何解决这个问题呢？具体操作如下：
首先我们需要给栈中的第一个数字添加一个符号‘+’。原因：当首个数据是正数时，添加‘+’不并影响计算，当首个数据是负数时，那么首个字符就会是‘-’，这样一来‘+’就需要更新为‘-’，同样不影响计算。而这样做的好处就是可以把对数据的处理统一起来，简化代码的逻辑。
接下来，需要一种思想：对于一个数据，比如：+9，-8等；他们是由符号和数字组成的。我们需要对每一个数据的符号和数字分别处理：
由于我们首先读取的是符号，所以需要将符号“存储起来”，等我们读取到这个符号的数字之后再对这个数据进行处理：
算法操作：
如果我们读取的符号是‘+’，我们需要将这个数据直接压栈；
如果我们读取的是‘-’，不同了，我们需要把这个数据的相反数压栈；
如果我们读取‘*’；需要将这个数与栈顶top相乘，pop原来的top，最后把这个数据压栈，作为新的top；
如果我们读取‘/’；需要：top/=数据，pop原来的top，把结果压入栈，作为新的top。
算法原理：
这一串字符串没有（），这就表示同优先级的运算符是按照结合性运算的。
‘+’，‘-’，‘*’，‘/’的结合性都是从左到右，与自然数学相同。
‘*’，‘/’的优先级高于‘+’，‘-’，这就表明需要先计算他们。
先计算‘+’，‘-’体现在：我们遇到‘+’，‘-’时，是直接与前一个数进行计算了。我们遇到的‘+’，‘-’一定是最左侧最先出现的‘+’，‘-’，是整个表达式中最先计算的部分，这就是我们的计算原理。
（比如下面的这一段表达式：
最先计算的是6*4，当我们读取到第一个‘*’时，6以及之前的数据已经压入栈中：
就下来读取到‘4’，按照算法，将栈顶的top*=4，再压入栈中，这就完成了第一个乘法操作：
对于除法操作，类似的，此时的栈顶数据top是乘法运算之后新压入的24,栈顶top/=2，结果是12，将12压入栈即可）
最终，遍历完字符串之后，将栈中的所有数据求和即可：
最终结果sum = 4 -3 +12 -123 +34。
总结：
1.遇到操作符：
更新记录符号（char类型）op；
2.遇到数字：
（1）先把数字提取出来，存储在整形变量tem中；
（2）分情况讨论，根据op的符号：
i，op == ‘+’，tem直接入栈；
ii，op == ‘-’，-tem入栈；
iii，op == ‘*’，直接乘到栈顶元素上；
iv，op == ‘/’，直接除到栈顶元素上。
参考代码：
class Solution { public: int calculate(string s) { int n = s.size(); int i = 0; char op = '+'; vector<int> st; while(i < n) { if(s[i] == ' ') ++i; else if(s[i] >= '0' && s[i] <= '9') //提取出数字 { int tem = 0; while(i < n && s[i] >= '0' && s[i] <= '9') { tem = tem * 10 + (s[i++] - '0'); } if(op == '+') { st.push_back(tem); } else if(op == '-') { st.push_back(-tem); } else if(op == '*') { st.back()*=tem; } else { st.back()/=tem; } } else { op = s[i]; i++; } } int sum = 0; while(!st.empty()) { sum += st.back(); st.pop_back(); } return sum; } };
完~
未经作者同意禁止转载