栈的介绍

栈的应用很多，可以检查程序中的符号是否都成对的出现，每一个右括号都应该有一个对应的左括号，可以用栈来实现进制的转换，当然还有今天的主题，利用栈来实现一个逆波兰计算器

逆波兰表达式

逆波兰表达式（Reverse Polish Notation 简称RPN），又称为后缀表达式，作为比较，我们常用的中序表达式表示方法是操作符位于操作数中间，比如 1 + 2，这里操作符+位于操作数1和2中间，而后缀表达式的表示方法是操作符位于两个操作数中间，比如1 2 +，这里的操作符+位于两个操作数1 2后边。总结来说RPN的特点就是表达式中各个运算是按运算符出现的顺序进行的，故无须使用括号来指示运算顺序

下边给出一些表达式的两种表示方法

1
2
3
1 + 2            1 2 +
1 + 2 * 3        1 2 3 * +
1 - ( 3 + 1 )    1 3 1 + -

从上面的例子可以看出：

  1. 在两种表示中，运算对象出现的顺序相同；
  2. 在后缀表示中，运算符按实际计算顺序从左到右排列，且每一运算符总是跟在其运算对象之后。

逆波兰表达示的优势就在于我们只需要两种简单的操作入栈和出栈，就可以实现简单表达式的运算

中序表达式转换为逆波兰表达式

首先需要分配两个栈，一个是用来存储临时操作符的栈S1，还有一个用来存储逆波兰表达式的栈S2

从中序表达式的左端取字符，逐一执行以下操作

  1. 若取出的字符是操作数，直接将操作数送入S2栈
  2. 若取出的字符是运算符，则将该运算符与S1栈栈顶元素比较，如果该运算符优先级大于S1栈栈顶运算符优先级，则将该运算符进S1栈，否则，将S1栈的栈顶运算符弹出，送入S2栈中，直至S1栈栈顶运算符低于（不包括等于）该运算符优先级，则将该运算符送入S1栈。
  3. 若取出的字符是“（”，则直接送入S1栈栈顶。
  4. 若取出的字符是“）”，则将距离S1栈栈顶最近的“（”之间的运算符，逐个出栈，依次送入S2栈，此时抛弃“（”。
  5. 重复上面的1~4步，直至处理完所有的输入字符
  6. 若取出的字符是“#”，则将S1栈内所有运算符（不包括“#”），逐个出栈，依次送入S2栈。
    完成以上步骤，S2栈便为逆波兰式输出结果。不过不要忘记S2栈要做一下逆序处理

计算的逻辑