转自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,这就是最后的运算结果
分享到:
相关推荐
本项目旨在实现一个能够解析并计算算术表达式的软件。具体目标如下: 1. **内容**:该程序应能正确计算含有括号的算术表达式,通过逐步解析并计算括号内的表达式,最终得出整个表达式的值。 - 举例说明:对于...
这个程序的主要目标是处理用户从键盘输入的算术表达式,对其进行解析并计算出正确结果。同时,它还具备显示输入序列和计算过程中栈变化的功能,以帮助用户理解程序的工作原理。为了增加程序的健壮性,它还包含了错误...
这里提到的`test_arithmetic.c`可能是一个包含实现算术表达式解析和求值的C源代码文件。`算术表达式求值.doc`可能是对这个过程的文档说明,详细解释了如何编写和测试程序。`说明.txt`则可能提供了更多关于如何理解和...
本文将深入探讨算术表达式求值的原理与实现,特别是利用堆栈这一数据结构来处理这类问题。 算术表达式是数学公式的一种表示方式,例如 `2 * (3 + 5)` 或 `(10 - 3) / 2`。在计算这些表达式时,我们需要遵循特定的...
在检查算术表达式时,我们可以通过以下步骤利用堆栈: 1. **初始化堆栈**:创建一个空堆栈,用于存储运算符。 2. **扫描表达式**:从左到右遍历表达式中的每一个字符。 3. **处理数字**:遇到数字时,将其视为一...
这里我们关注的是“利用堆栈对表达式求值”的方法,这是一种常见的算法,尤其适用于简单的算术表达式。堆栈是一种后进先出(LIFO)的数据结构,非常适合处理具有运算符优先级的表达式。 标题“利用堆栈表达式求值源...
通过这种方式,我们可以有效地解析和计算简单的LISP算术表达式,这不仅巩固了数据结构中堆栈的应用,还加深了对LISP语言基础的理解。在实现过程中,还需要考虑错误处理和异常情况,确保程序的健壮性和用户体验。
在算术表达式求值中,我们可以利用栈来实现逆波兰表示法(Reverse Polish Notation, RPN)求值。逆波兰表示法是一种没有括号的表达方式,运算符位于其操作数之后。例如,表达式 "2 + 3 * 4" 在逆波兰表示法下为 "2 3...
在这个项目中,我们利用了堆栈的数据结构来实现表达式的计算,这是一种非常有效的方法。 首先,我们要理解堆栈(Stack)的基本概念。堆栈是一种后进先出(LIFO,Last In First Out)的数据结构,类似于现实生活中的...
在处理算术表达式时,我们可以将其转换为一个二叉树,其中叶子节点代表操作数(数字),而内部节点代表运算符。例如,表达式 "2 + 3 * 4" 可以转换为一个二叉树,加号节点的左孩子是数字2,右孩子是一个乘法节点,...
在编程领域,尤其是在易语言这样的国产编程环境中,利用堆栈进行表达式计算是一种常见的方法。堆栈是一种具有“后进先出”(LIFO,Last In First Out)特性的数据结构,非常适合处理需要逆波兰表示法(Reverse ...
1. **表达式解析**:输入的后缀表达式需要被解析成一个个单独的数字和运算符。这通常通过分隔符(如空格)来完成。解析过程中,可以使用字符串的切片或正则表达式来提取每个元素。 2. **栈数据结构**:栈是后缀...
在数据结构设计部分,使用了递归结构来构建四元式,并利用堆栈来存储和输出四元式序列。具体实现中,有两个栈:SYN用于存储操作符,SEM用于存储运算对象。代码示例展示了如何处理加减乘除操作,生成四元式,并在遇到...
考虑一个简单的算术表达式的计算问题:“5+6/2-3*4”。为了正确解析该表达式,我们需要区分运算数和运算符,并考虑运算符的优先级。例如,在计算过程中,“/”和“*”的优先级高于“+”和“-”。 **中缀表达式**指...
在这个案例中,我们将聚焦于“堆栈”这一特定的数据结构,并探讨如何利用它来实现一个堆栈计算器,处理基本的算术表达式。堆栈是一种具有“后进先出”(LIFO,Last In First Out)特性的数据结构,类似于现实生活中...
堆栈计算器是利用堆栈这一特性来处理数学表达式的计算。在本案例中,计算器设计了两个堆栈:一个用于存储运算符,另一个用于存储数字(运算数)。这种设计能够有效地处理包括括号在内的复杂算术表达式。 #### 二、...
在编程语言中,主要有算术表达式(如2+3)、关系表达式(如x>y)、逻辑表达式(如a&&b)和条件表达式(如a?b:c)。这些表达式通过运算符连接,形成可以求值的语句。 其次,表达式计算涉及到语法分析,这通常由词法...
数据结构和算法是计算机科学的...总之,利用堆栈进行括号匹配是一种常见的算法应用,它体现了数据结构与算法在实际问题解决中的价值。理解并掌握这一方法,对于提升编程能力和解决类似问题的能力有着积极的推动作用。