堆栈解析算术表达式

中缀表达式就是通常所说的算术表达式,比如(1+2)*3-4。

后缀表达式是指通过解析后,运算符在运算数之后的表达式,比如上式解析成后缀表达式就是12+3*4-。这种表达式可以直接利用栈来求解。
中缀->后缀 就是运算符的出入栈,操作数直接输出,运算符按优先级高(低)是入(出)栈。


运算符的优先级

优先级 运算符
1 括号()
2 负号-
3 乘方**
4 乘*,除/,求余%
5 加+,减-
6 小于<,小于等于<=,大于>,大于等于>=
7 等于==,不等于!=
8 逻辑与&&
9 逻辑或||
堆栈解析算术表达式的过程

中缀表达式翻译成后缀表达式的方法如下:

(1)从右向左依次取得数据ch。

(2)如果ch是操作数,直接输出。

(3)如果ch是运算符(含左右括号),则:
      a:如果ch = '(',放入堆栈。
      b:如果ch = ')',依次输出堆栈中的运算符,直到遇到'('为止。
      c:如果ch不是')'或者'(',那么就和堆栈顶点位置的运算符top做优先级比较。
           1:如果ch优先级比top高,那么将ch放入堆栈。
           2:如果ch优先级低于或者等于top,那么输出top,然后将ch放入堆栈。

(4)如果表达式已经读取完成,而堆栈中还有运算符时,依次由顶端输出。

如果我们有表达式(A-B)*C+D-E/F,要翻译成后缀表达式,并且把后缀表达式存储在一个名叫output的字符串中,可以用下面的步骤。

(1)读取'(',压入堆栈,output为空
(2)读取A,是运算数,直接输出到output字符串,output = A
(3)读取'-',此时栈里面只有一个'(',因此将'-'压入栈,output = A
(4)读取B,是运算数,直接输出到output字符串,output = AB
(5)读取')',这时候依次输出栈里面的运算符'-',然后就是'(',直接弹出,output = AB-
(6)读取'*',是运算符,由于此时栈为空,因此直接压入栈,output = AB-
(7)读取C,是运算数,直接输出到output字符串,output = AB-C
(8)读取'+',是运算符,它的优先级比'*'低,那么弹出'*',压入'+",output = AB-C*
(9)读取D,是运算数,直接输出到output字符串,output = AB-C*D
(10)读取'-',是运算符,和'+'的优先级一样,因此弹出'+',然后压入'-',output = AB-C*D+
(11)读取E,是运算数,直接输出到output字符串,output = AB-C*D+E
(12)读取'/',是运算符,比'-'的优先级高,因此压入栈,output = AB-C*D+E
(13)读取F,是运算数,直接输出到output字符串,output = AB-C*D+EF
(14)原始字符串已经读取完毕,将栈里面剩余的运算符依次弹出,output = AB-C*D+EF/-

计算算术表达式

后缀表达式按照下面的流程来计算。
现在是操作数入栈,运算符进行两两比较。

(1)从左向右扫描表达式,一个取出一个数据data
(2)如果data是操作数,就压入堆栈
(3)如果data是操作符,就从堆栈中弹出此操作符需要用到的数据的个数,进行运算,然后把结果压入堆栈
(4)如果数据处理完毕,堆栈中最后剩余的数据就是最终结果。

比如我们要处理一个后缀表达式1234+*+65/-,那么具体的步骤如下。

(1)首先1,2,3,4都是操作数,将它们都压入堆栈
(2)取得'+',为运算符,弹出数据3,4,得到结果7,然后将7压入堆栈
(3)取得'*',为运算符,弹出数据7,2,得到数据14,然后将14压入堆栈
(4)取得'+',为运算符,弹出数据14,1,得到结果15,然后将15压入堆栈
(5)6,5都是数据,都压入堆栈
(6)取得'/',为运算符,弹出数据6,5,得到结果1.2,然后将1.2压入堆栈
(7)取得'-',为运算符,弹出数据15,1.2,得到数据13.8,这就是最后的运算结果
上一篇:渗透测试中php代码漏洞挖掘


下一篇:《PHP精粹:编写高效PHP代码》——2.4节PHP数据库对象