逆波兰表达式算法原理记录

原始逆波兰式算法(未考虑负数、函数调用情况)

1、从左至右扫描一中缀表达式。
2、若读取的是操作数,则判断该操作数的类型,并将该操作数存入操作数堆栈
3、若读取的是运算符
      (1) 该运算符为左括号"(",则直接存入运算符堆栈。
      (2) 该运算符为右括号")",则输出运算符堆栈中的运算符到操作数堆栈,直到遇到左括号为止,此时抛弃该左括号。
      (3) 该运算符为非括号运算符:
      (a) 若运算符堆栈栈顶的运算符为左括号,则直接存入运算符堆栈。
      (b) 若比运算符堆栈栈顶的运算符优先级高,则直接存入运算符堆栈。
      (c) 若比运算符堆栈栈顶的运算符优先级低或相等,则输出栈顶运算符到操作数堆栈,直至运算符栈栈顶运算符低于(不包括等于)该运算符优先级,或为左括号,
           并将当前运算符压入运算符堆栈。
4、当表达式读取完成后运算符堆栈中尚有运算符时,则依序取出运算符到操作数堆栈,直到运算符堆栈为空。
 

 
改进的逆波兰式算法(考虑负数、函数调用情况)

1.构建两个栈Operand(操作数栈)和Operator(操作符栈)和一个LAST_TOKEN标记字段。

2.扫描给定的字符串,扫描时注意跳过空格,提取完整的操作数、操作符和函数。

3.如果获得一个运算符(用B代替)首先构造响应的运算符,构造时需要比较LAST_TOKEN记录字段,来判断重载的操作符的含义,比如如果LAST_TOKEN是数字,那么“-”就是一    个数学运算符,如果LAST_TOKEN是运算符,那么要看“-”后面是不是数字,如果是数字,则认为“-”是“负号”。构造好Operator后和Operator栈栈顶元素(用A替代)比      较:

   1)如果A不存在,则把B压入Operator栈中;

   2)如果B是一个左括号,则忽略A和B的优先级比较,把B压入Operator栈。

   3)如果B是逗号,同样忽略A和B的比较,把B压入Operator栈。

   4)如果B是一个右括号,则把Operator栈顺序出栈,然后把弹出的元素顺序压入Operand栈中,出栈是需要判断逗号情况,如果是逗号,则不入栈,记录逗号个数,直到栈顶弹出       的是左括号,括号不入Operand栈中。之后看Operator栈顶元素,如果栈顶元素是函数类型,则把函数Operator出栈然后将逗号个数+1构造数字操作数压入Operand栈中,然       后把函数Operator也压入Operand栈中。

   5)如果A是左括号,则把B直接压入Operator栈。

   6)如果B优先级比A高,则把B直接压入Operator栈。

   7)如果B优先级低于或等于A的优先级,则把A出栈然后压入Operand栈,反复进行此步骤直到栈顶优先级高于B的优先级或者栈顶是一个括号。

4.扫描完毕后,把Operator栈的元素依次出栈,然后依次压入Operand栈中。


 
 
 
原文地址:https://www.cnblogs.com/you-you-111/p/7574237.html