四则运算
1. 中缀表达式转后缀表达式
中缀表达式 9+(3-1)×3+10÷2 转化为后缀表达式 9 3 1 - 3 * + 10 2 / +
规则
- 遇到数字就直接输出到后缀表达式中，遇到操作符就判断其优先级，并将其压入栈中
- 如果栈顶元素的优先级大于等于当前操作符，则先将栈顶元素弹出并输出到后缀表达式中，再将当前操作符压入栈中。
- 如果遇到了左括号，则直接将其压入栈中，如果遇到了右括号，则弹出栈中的元素，直到遇到了左括号为止，并将这些元素输出到后缀表达式中。
- 最后，将栈中剩余的元素依次弹出，并输出到后缀表达式中。
演示
- 初始化一空栈，用来对符号进出栈使用。
- 第一个字符是数字9，输出9，后面是符号“+”，进栈。
- 第三个字符是“(”，依然是符号，因其只是左括号，还未配对，故进栈。
- 第四个字符是数字3，输出，总表达式为93，接着是“-”，进栈。
- 接下来是数字1，输出，总表达式为 9 3 1，后面是符号“)”，此时，我们需要去匹配 此前的“(”，所以栈顶依次出栈，并输出，直到“(”出栈为止。此时左括号上方只有“-”， 因此输出“-”。总的输出表达式为 9 3 1 -。
- 紧接着是符号“×”，因为此时的栈顶符号为“+”号，优先级低于“×”，因此不输出，“×”进栈。接着是数字3，输出，总的表达式为 9 3 1 - 3。
- 之后是符号“+”，此时当前栈顶元素“×”比这个“+”的优先级高，因此栈中元素出栈并输出（没有比“+”号更低的优先级时一直出栈，所以全部出栈），总输出表达式为9 3 1 - 3 × +。然后将当前这个符号“+”进栈。也就是说，前6张图的栈底的“+”是指中缀表达式中开头的9 后面那个“+”，而下图的左图中的栈底（也是栈顶）的“+”是指“9+(3-1)×3+”中的最后 一个“+”。
- 紧接着数字10，输出，总表达式变为9 3 1 - 3 × + 10。后是符号“÷”，所以“/”进栈。
- 最后一个数字2，输出，总的表达式为9 3 1 - 3 × + 10 2。
- 因已经到最后，所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为 9 3 1 - 3 × + 10 2 / +。
2. 后缀表达式计算结果
规则
- 遍历后缀表达式，如果遇到数字则直接入栈，如果遇到操作符，则弹出栈顶的两个元素，进行计算后将结果入栈。
- 最终，栈内剩余的元素就是整个表达式的计算结果。
演示
- 初始化一个空栈。此栈用来对要运算的数字进出使用。
- 后缀表达式中前三个都是数字，所以9、3、1进栈。
- 接下来是“-”，所以将栈中的1出栈作为减数，3出栈作为被减数，并运算3-1得到 2，再将2进栈。
- 接着是数字3进栈。
- 后面是“*”，也就意味着栈中3和2出栈，2与3相乘，得到6，并将6进栈。
- 下面是“+”，所以栈中6和9出栈，9与6相加，得到15，将15进栈。
- 接着是10与2两数字进栈。
- 接下来是符号“/”，因此，栈顶的2与10出栈，10与2相除，得到5，将5进栈。
- 最后一个是符号“+”，所以15与5出栈并相加，得到20，将20进栈。
- 结果是20出栈，栈变为空。