链表与栈的典型应用——简单计算机的实现

先来看一个粗糙的简单计算器的实现。他只支持加减乘除,并且一次只能对两个小于10的正整数做一次运算

这是一个粗糙的实现,但是但是仍旧有一些要点体现在上面,比如对 表达式的分析中使用了while(str[i] && str[i]!=’\n’)我们首先要判断是不是到表达式字符串 的结尾了,如果不是还要判断是不是’\n’字符。因为调用fgets输入表达式时回车键也被存储了。

上面的程序只能进行一次 两个小于十的正整数 的加减乘除运算。如下

当然,这连个简单的计算器都算不上。
1: 如果我要计算 2+3+4怎么办。也就是说上面的不支持大于两个操作数的运算
2 :如果我要 计算2的立方怎么办 。也就是说上面支持的运算太少了,这个其实问题不大。因为我们通过加单的添加就可以了。所以后面的正真实现中我们还是只实现了加减乘除四个典型运算以及带括号的运算
3 :如果我要计算 2+3*4怎么办?有的人可能会问,这有什么怎么办了。计算就好了。但是我们知道应该先算 3*4 然后再 +2

但是计算器不知道啊。也就是说上面的并未支持优先级。这在windows自带的计算机上有体现在查看里面将计算器切换到标准型

再切换到科学型。

很显然,标准型并未支持优先级运算,他只是简单的从左往右运算

4 :如果我要计算 20+10怎么办,也就是说运算数可以是任意的并不固定为小于十的正整数,因为我们输入的一个连续的 表达式字符串。
那么就需要更复杂一点的语句分析才能提取出正真的数字。当然后面的正真实现中,也只是实现了 整形所能表示的正整数的相加,并未实现小数,负数之类。当然他们原理都是相同的,只是在表达式的分析上复杂一些而已。

所以,即使是一个简单的计算器,也应该上面的四个要求。
1,2, 4,的要求主要在表达式字符串的分析上,也就是从里面分析出 字符 和数字。无非是语法分析变复杂一点。
问题核心是在 如何运算符的优先级上。

这就需要了解 后缀(逆波兰)表达式。
定义:不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,
严格从左向右进行(不再考虑运算符的优先规则,如:(2 + 1) * 3 , 即2 1 + 3 *

我们知道计算机并不知道什么优先级。最简单的它只会从左到有读取然后运算。
那么根据上面 后缀表达式的定义。如果能将表达是转换成后缀表达式,那么运算就简单了。可以使用一个栈来实现。
比如:3+12*2-(6+1)*2;
转换成后缀表达式 3 12 2 * + 6 1 + 2 * –
使用一个栈,然后从左到右遍历,遇到数字我们就其入栈,遇到运算符,就出栈两个数字然后做运算,并将运算结构入栈。这样一直下去到最后。栈中存放的就为最终的结果

也就是说如果得到了后缀表达式那么就可以用上面的方法来从左到右计算了。而不存在优先级的问题了
那么,现在问题就变成了怎么将表达式变成计算机易于计算的后缀表达式,这里同样是用到栈来实现的。
下面我们通过对 + *以及( )这几个典型的运算符的处理 来阐述转换成后缀表达式的一般原理。

我们假设表达式是合法的。当读到一个操作数的时候,立即把他放到输出中。
遇到其他运算符时”+” ,”*” , “(” 那么久从栈中弹出元素直到当前栈顶元素的优先级比当前遇到的运算符低,然后再将该运算符入栈需要注意
的一点是 除非是在处理一个右括号’)’否则绝不从栈中移走左括号'(‘。
如果遇到右括号’)’,那么就将栈元素弹出并写到输出,直到遇到一个对应的左括号。注意:这时候右括号不入栈,弹出的左括号也不输出。而是仅仅丢弃他们
最后当我们读到表达式的结尾时,再将栈中的元素依次弹出写到输出中直到栈空变得到了后缀表达式

比如 a+b*c+(d*e+f)*g
后缀表达式为: a b c * + d e * f + g * +

转换过程如下

得到后缀表达式后一切就简单了,计算机只需想上面说的那样从左到右简单计算就行了。

下面我们对 计算器编写过程中的几个核心部分的代码详细说明
整体思路是 从键盘得到一个字符串形式的表达式,然后从左到右对其进行分析,依次分离出数字和运算符然并创建对应节点,
然后像上面介绍的放法一样,如果是数字就 插入到一个链表中(这里并不输出而是放到链表中供后续使用),如果是运算符,就放入栈中。
最终当分析表达式结尾时,弹出栈中所有元素并依此插入链表中,最终链表就是我们需要的后缀表达式。

然后对链表从左到右遍历并使用之前所说的对后缀表达式的计算方法。计算出最终结果
需要注意的是,我们没有做错误检查,所以输入的表达式必须是合法的

求后缀表达式的代码注释

根据后缀表达是求运算结果的注释:

测试结果如下
第二行给出了后缀表达式

下面是所有代码实现

head.h

head.c

测试代码

1 3 收藏 1 评论

相关文章

可能感兴趣的话题



直接登录
最新评论
跳到底部
返回顶部