转自http://www.cnblogs.com/flyingbread/archive/2007/02/03/638932.html
1 本文目标
分析用堆栈解析算术表达式的基本方法。给出的示例代码能解析任何包括+,-,*,/,()和0到9数字组成的算术表达式。
2 中缀表达式和后缀表达式
中缀表达式就是通常所说的算术表达式,比如(1+2)*3-4。
后缀表达式是指通过解析后,运算符在运算数之后的表达式,比如上式解析成后缀表达式就是12+3*4-。这种表达式可以直接利用栈来求解。
3 运算符的优先级
优先级 运算符
1 括号()
2 负号-
3 乘方**
4 乘*,除/,求余%
5 加+,减-
6 小于<,小于等于<=,大于>,大于等于>=
7 等于==,不等于!=
8 逻辑与&&
9 逻辑或||
大致的规律是,一元运算符 > 二元运算符 > 多元运算符。
4 利用堆栈解析算术表达式的过程
中缀表达式翻译成后缀表达式的方法如下:
(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/-
5 计算算术表达式
当有了后缀表达式以后,运算表达式的值就非常容易了。可以按照下面的流程来计算。
(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,这就是最后的运算结果
分享到:
相关推荐
逆波兰表达式用堆栈实现,读入表达式的值,利用堆栈计算该表达式的值,同时校验后缀表达式是否正确。
大部分的堆栈类实现表达式计算的例程都只能实现个位数的运算。在本例程中,创建了一个成员变量可为double型数字或是char型运算符的类,再建立该类的堆栈,最终可实现多位数的运算。
这个是用堆栈的方式来实现算术表达式,有良好的用户界面
利用栈来实现表达式自动计算,方法一是:先把中缀表达式变成后缀表达式再计算;方法二是:构造两个栈扫描一遍直接出结果!
利用堆栈计算表达式的值,如:3×5-2+3×8/2实现+、-、×、/、(、)运算
C++语言,利用堆栈实现波兰表达式实现后缀表达式计算。
(1) 从键盘读入一个合法的算术表达式,输出正确的结果。(2) 显示输入序列和栈的变化过程。(3) 考虑算法的健壮性,当表达式错误时,要给出错误原因的提示
Java 实例 - 利用堆栈将中缀表达式转换成后缀表达式源代码-详细教程.zip
算术表达式求值(用到堆栈,没用模版) 程序运用运算符栈、运算数栈以及优先级阵列等算法实现:对输入的算术表达式求值后输出。主程序结构简单,算法各函数功能明确。考虑到程序模版操作给程序可读性带来障碍,所以...
堆栈实现后缀表达式算法,在winform基础上实现后缀表达式计算器
中缀表达式转换为后缀表达式,删除堆栈元素中缀表达式转换为后缀表达式,删除堆栈元素中缀表达式转换为后缀表达式,删除堆栈元素中缀表达式转换为后缀表达式,删除堆栈元素中缀表达式转换为后缀表达式,删除堆栈元素...
c语言实现的括号匹配算法 无括号算术表达式处理算法 #include "seqstack.h" #include "stdio.h" void BracketMatch(char *str); void BracketMatch(char *str) /* str[]中为输入的字符串,利用堆栈技术来检查该...
数据结构课程作业 实现+-*/四则运算和^ 按照优先级来计算
VC++2012编程演练数据结构《5》堆栈实现解析任意计算表达式
后缀表达式求值 定义堆栈
这是用堆栈实现中序表达式的计算过程,定义了+,-,*,/,%这几种基本用算,代码有助于理解堆栈的使用过程
主要用堆栈来实现数学表达式的解析功能 理解编译原理的过程
c++使用堆栈实现中缀表达式转后缀表达式
利用堆栈对表达式求值的源代码,适合数值是一位的表达式!
在该程序中,使用了堆栈的功能来检查一个计算表达式的正确性,这样能够在设计算术表达式的算法的时候,是回用的的。