维护好以括号分段的运算符单调栈，分段结算以至最终。
三道基本计算器由浅入深
Leetcode上有三道“基本计算器”题，分别是：
| 题目 | 区别 | 例子 | 难度 |
|---|---|---|---|
| 224. 基本计算器 | 只包含加减法及括号 | 3+(2+5)-(4+2) | 困难 |
| 227. 基本计算器 II | 包括加减乘除但是不包含括号 | 3+4*5+6 | 中等 |
| 772. 基本计算器 III | 包含所有的加减乘除及括号运算 | (3+4)*(5+6) | 困难 |
其实这一系列题目最大的难点就是优先级的问题。假设不存在优先级，比如只包含加减号不包含乘除号或者括号，那么只要线性地从左到右扫描即可。但优先级的存在使得我们无法按顺序求解。因此我们需要找到一种行之有效的方式，按照一定的规则暂存尚未处理的操作数和操作符，再按照一定的顺序将暂存的内容取出，从而求出最终答案。让我们按照如下的顺序考虑这三题。
227. 基本计算器II
我们先来考虑227题，题目如下：
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。 整数除法仅保留整数部分。
示例 1：输入：s = “3+2*2” 输出：7
示例 2：输入：s = “ 3/2 “ 输出：1
示例 3：输入：s = “ 3+5 / 2 “ 输出：5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/basic-calculator-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法1. 领导后进，维护符号单调栈
因为涉及到状态的存储，我们考虑用栈来辅助我们进行求解。如果维护两个栈：oprands和ops来分别保存操作数和操作符的状态。那么当操作符栈为空，或者当前要压入这个栈的符号相比于栈顶的符号优先级较高时，由于当所有符号压入栈之后，最终会按照相反的顺序后进先出（LIFO）地弹出，这里后进的高优先级操作符会先行处理，符合计算要求，因此可以直接压入栈中不需要额外步骤。但是如果当前要压入的符号优先级较低，那么就要把此时在栈顶优先级更高的符号依次弹出计算，直到符号栈内为空或者优先级与当前运算符相同的时候，再把当前运算符压栈，这样当扫描完成后出栈的时候，即使后进的符号先计算也不会影响结果。
所以其实这里的符号栈是一个符合符号优先级的单调栈（单调不减），只要后进的“领导”优先级不低于之前的符号，那就不需要额外处理，栈的性质保证了后进的符号会得到高优先级的对待。
解法2. 乘除先走，加减留堂慢慢算
此题还有另一种解法：由于只包含加减乘除，其实只有两级的优先级，所以我们可以暂存低优先级的加减法。第一遍循环中，当我们遇到乘除号的时候可以确定一定是当前最高的优先级，立即计算。因为oprands栈中已经保存了之前的操作数，此时只需要取出左侧操作数，与右侧操作数计算后将结果压入栈即可。而如果此时遇到的是加减法计算则需要暂时先压入ops栈中，以便后续计算。当第一遍循环结束后，操作符栈中将只有加减法，此时只需要依次计算栈中的加减法即可得出结果。
224. 基本计算器
实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。
示例 1：输入：s = “1 + 1” 输出：2
示例 2：输入：s = “ 2-1 + 2 “ 输出：3
示例 3：输入：s = “(1+(4+5+2)-3)+(6+8)” 输出：23
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/basic-calculator
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法1. 左括号进，成双成对再出栈
在思考过227题后，只包含加减号及括号的题目解法也就很容易想到了。由于计算的顺序可能会因为后面尚未出现的括号而改变，比如4-(3+2)，我们只有先计算了最里面的括号包含的算式3+2后才能计算外层的算式，因此无论我们遇到操作数或者操作符的时候，都应该先压入栈中，直到遇到了右括号时，意味着一段不包含括号的算式的结束。从这个右括号向前追溯到最近的左括号，这中间的算式是只包含加减法的基本计算，可以从栈中取出，计算出结果后再压入栈中，这样将消去一对括号。而由于左右括号一定是匹配的，因此一次循环过后，符号栈中将又只存在加减号，与上题类似，只需要按序计算即可得出结果。
解法2. 非正即负，巧用栈来记阴阳
本题其实还有另一种更为取巧的做法，由于只有加减号和括号，如果我们尝试消去这类算式中的括号，其如下特性让我们可以加以利用。
- 如果括号前为加号，则可以直接去掉括号
- 如果括号前为减号，则括号内符号取反即可 因此我们可以把这题简化，考虑如果去掉所有括号，并记录下由于之前括号前的符号对当前位置的正负影响，此外直接按照顺序求解表达式即可。
772. 基本计算器 III
实现一个基本的计算器来计算简单的表达式字符串。
表达式字符串只包含非负整数，算符 +、-、*、/ ，左括号 ( 和右括号 ) 。整数除法需要 向下截断 。
你可以假定给定的表达式总是有效的。所有的中间结果的范围为 [-231, 231 - 1] 。
示例 1：输入：s = “1+1” 输出：2
示例 2：输入：s = “6-4/2” 输出：4
示例 3：输入：s = “2(5+52)/3+(6/2+8)” 输出：21
示例 4：输入：s = “(2+63+5-(314/7+2)*5)+3” 输出：-12
示例 5：输入：s = “0” 输出：0
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/basic-calculator-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
本题即是这个系列的最终完整形态：包含括号的四则运算表达式。在之前两题的基础上考虑这一题，难度则会有所降低，因为前两题的解法1告诉了我们如下道理：
- 道理1. 加减号在乘除号面前是没有地位的，遇到了需要先去栈里待着，押后处理。如果栈里已经有了更高优先级的计算，还需要先将之前高优先级的符号请出来先行计算后方可入栈，保证符号栈的“单调性”
- 道理2. 左括号是没有地位的，无论什么情况都需要先去栈里待着，直到右括号出现。此时按顺序往回清算，直到遇到了最近的左括号并将其释放。右括号的作用与表达式结束后整体清算相同
道理1的单调性保证了道理2中，无论是因为右括号还是整个算式结束导致的对栈内符号的弹出计算都是按顺序的。两者结合起来即可解决完整形态的基本计算器III这一问题。
小结
我们可以看到，这三题的解法其实是可以做到一脉相承的。但是我们也能注意到，前两题其实都不止一种解法，甚至也不止我们这里列出的两种方法。但是并非所有的解法都是可以继续扩展的，在本系列的情形中，基础题可以扩展的解法反倒不是最简单、最容易想出的解法。因此我们在做题的时候，不仅需要利用一些特殊的条件做到快速解题，还需要将类似的题结合起来，不断升级复杂度，才能够看到简化情形背后清晰的脉络。
总结起来基本计算器的解法就是：在第一次从左到右扫描过程中，维护一个以左括号分段的运算符单调栈，并以右括号以及字符串的结尾作为当前分段单调栈结算的符号，最终完成整个算式的运算。