【数据结构基础整理】栈应用--02：逆波兰算法

0x01.关于逆波兰算法

中缀表达式：

• 中缀表达式表示操作符、运算符在需要计算的数值中间

后缀表达式：

• 在20世纪30年代，波兰逻辑学家Jan.Lukasiewicz发明了一种不需要括号的后缀表达式，我们通常把它称为逆波兰表达式(RPN)，逆波兰表达式也叫后缀表达式。

后缀表达式的优点：

• 去除原来表达式中的括号，因为括号只指示运算顺序，不是实际参与计算的元素。
• 使得运算顺序有规律可寻，计算机能编写出代码完成计算。

0x02.逆波兰算法的原理

中缀表达式转换为后缀表达式：

• 首先我们要建立一个集合 sList 来存放例子中的数据和操作符号，一个栈opStack来存放中间的操作符号，一个集合dList 来存放最后的转换结果。
• 从sList中取出一个元素A然后进行以下判断： 
• 如果A是数字，则直接存如dList 
• 如果A是运算符，则和opStack栈顶的元素进行运算优先级比较 
• 如果A的优先级高于栈顶运算符优先级，则将A入栈opStack 
• 如果A的优先级低于或等于栈顶运算符的优先级，那么将栈顶的元素出栈存入dList，重复此步骤直到栈顶的运算符优先级低于当前运算符,然后A入栈。 
• 如果A是左括号“（”直接入栈，如果是右括号“）”，则将opStack中的运算符弹出存入dList，直到弹出左括号，左右括号均不存入dList，左括号永远不会弹出，直到遇到右括号（针对括号内的元素执行步骤同以上步骤）。 
• 不断重复以上步骤直到表达式解析完成。 

运算后缀表达式：

• 首先建立一个结果栈rStack，然后将dList中的元素依次取出，进行入栈操作，如果碰到操作符就从栈中取出两个元素进行运算，结果入栈，依次重复。