题目描述
Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
Example 1:
Input: "1 + 1" Output: 2
Example 2:
Input: " 2-1 + 2 " Output: 3
Example 3:
Input: "(1+(4+5+2)-3)+(6+8)" Output: 23
Note:
- You may assume that the given expression is always valid.
-
Do not use the
evalbuilt-in library function.
思路：
在做这个之前我们需要先了解一下算数表达式转为后缀表达式以及对后缀表达式用逆波兰的计算过程。
一.根据中缀表达式计算后缀表达式
https://blog.csdn.net/lcl497049972/article/details/83061274
中缀表达式“9+(3-1)*3+10/2”转化为后缀表达式“9 3 1-3*+ 10 2/+”
规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于找顶符号（乘除优先加减）则栈顶元素依次出找并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。
下面我们来具体看看这个过程。
1. 初始化一空栈，用来对符号进出栈使用。
2. 第一个字符是数字9，输出9，后面是符号“+”，进栈。
3. 第三个字符是“(”,依然是符号，因其只是左括号，还未配对，故进栈。
4. 第四个字符是数字3，输出，总表达式为9 3,接着是“-”进栈。
5. 接下来是数字1，输出，总表达式为9 3 1，后面是符号“)”，此时，我们需要去匹配此前的“(”，所以栈顶依次出栈，并输出，直到“(”出栈为止。此时左括号上方只有“-”，因此输出“-”，总的输出表达式为9 3 1 -
6. 接着将符号“*”，因为此时的栈顶符号为“+”号，优先级低于“*”，因此不输出。将“*”压栈；然后是数字3，输出，总的表达式为9 3 1 - 3 。
7. 之后是符号“+”，此时当前栈顶元素比这个“+”的优先级高，因此栈中元素出栈并输出（没有比“+”号更低的优先级，所以全部出栈），总输出表达式为 9 3 1 - 3 * +.然后将当前这个符号“+”进栈。也就是说，前6张图的栈底的“+”是指中缀表达式中开头的9后面那个“+”，而下图中的栈底（也是栈顶）的“+”是指“9+(3-1)*3+”中的最后一个“+”。
8. 紧接着数字10，输出，总表达式变为9 3 1-3 * + 10。
9. 最后一个数字2,输出，总的表达式为 9 3 1-3*+ 10 2
10. 因已经到最后，所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为 9 3 1-3*+ 10 2/+
计算机运算的步骤是：
- 将中缀表达式转化为后缀表达式（栈用来进出运算的符号）。
- 将后缀表达式进行运算得出结果（栈用来进出运算的数字）。
二、后缀表达式的计算过程
https://www.cnblogs.com/jiu0821/p/6692878.html
后缀表达式：9 3 1-3*+ 10 2/+
-
规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。
详细步骤：
1. 初始化一个空栈。此桟用来对要运算的数字进出使用。
2. 后缀表达式中前三个都是数字，所以9、3、1进栈。
3. 接下来是减号“-”，所以将栈中的1出栈作为减数，3出栈作为被减数，并运算3-1得到2，再将2进栈。
4. 接着是数字3进栈。
5. 后面是乘法“*”，也就意味着栈中3和2出栈，2与3相乘，得到6，并将6进栈。
6. 下面是加法“+”，所以找中6和9出找，9与6相加，得到15，将15进栈。
7. 接着是10与2两数字进栈。
8. 接下来是符号因此，栈顶的2与10出栈，10与2相除，得到5，将5进栈。
9. 最后一个是符号“+”，所以15与5出找并相加，得到20，将20进栈。
10. 结果是20出栈，栈变为空。