逆波兰表达式

摘自:https://zh.wikipedia.org/wiki/%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E7%A4%BA%E6%B3%95

逆波兰表示法(Reverse Polish notation,RPN,或逆波兰记法),是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式,在逆波兰记法中,所有操作符置于操作数的后面,因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。

逆波兰记法中,操作符置于操作数的后面。例如表达“三加四”时,写作“3 4 +”,而不是“3 + 4”。如果有多个操作符,操作符置于第二个操作数的后面,所以常规中缀记法的“3 – 4 + 5”在逆波兰记法中写作“3 4 – 5 +”:先3减去4,再加上5。使用逆波兰记法的一个好处是不需要使用括号。例如中缀记法中“3 – 4 * 5”与“(3 – 4)*5”不相同,但后缀记法中前者写做“3 4 5 * -”,无歧义地表示“3 (4 5 *) −”;后者写做“3 4 – 5 *”。
逆波兰表达式的解释器一般是基于堆栈的。解释过程一般是:操作数入栈;遇到操作符时,操作数出栈,求值,将结果入栈;当一遍后,栈顶就是表达式的值。因此逆波兰表达式的求值使用堆栈结构很容易实现,和能很快求值。
注意:逆波兰记法并不是简单的波兰表达式的反转。因为对于不满足交换律的操作符,它的操作数写法仍然是常规顺序,如,波兰记法“/ 6 3”的逆波兰记法是“6 3 /”而不是“3 6 /”;数字的数位写法也是常规顺序。

代码[编辑]

  • while有输入符号
    • 读入下一个符号
    • IF是一个操作数
      • 入栈
    • ELSE IF是一个操作符
      • 有一个先验的表格给出该操作符需要n个参数
      • IF堆栈中少于n个操作数
        • (错误)用户没有输入足够的操作数
      • Else,n个操作数出栈
      • 计算操作符。
      • 将计算所得的值入栈
  • IF栈内只有一个值
    • 这个值就是整个计算式的结果
  • ELSE多于一个值
    • (错误) 用户输入了多余的操作数