《利用栈实现c语言计算器》由会员分享,可在线阅读,更多相关《利用栈实现c语言计算器(4页珍藏版)》请在金锄头文库上搜索。
1、栈的应用:C 实现简单计算器(表达式的计算)作为栈的著名应用,表达式的计算可以用下面方法实现:首先建立两个栈,操作数栈 NUM_S 和运算符栈 OPR_S。其中,操作数栈用来存储表达式中的操作数;运算符栈用来存储表达式中的运算符。可以用字符=来表示表达式结束符。自左至右的扫描待处理的表达式,并假设当前扫描到的符号为 W,根据不同的符号W 做如下不同的处理: 1.若 W 为操作数,则将 W 压入操作数栈 NUM_S,且继续扫描下一个字符; 2.若 W 为运算符,则根据运算符的性质做相应的处理: (0)若符号栈为空,无条件入栈当前指针指向的字符(1)若 w 为不大于运算符栈栈顶的运算符,则从操作数
2、栈 NUM_S 中弹出两个操作数,设先后弹出的操作数为 a、b,再从运算符栈OPR_S 中弹出一个运算符,比如为+,然后作运算 a+b,并将运算结果压入操作数栈 NUM_S。(2)若 w 为左括号或者运算符的优先级大于运算符栈栈顶的运算符,则将运算符 W压入运算符栈 OPR_S,并继续扫描下一个字符。(3)若运算符 W 为右括号,循环操作(设先后弹出的操作数为 a、b,再从运算符栈OPR_S 中弹出一个运算符,比如为+,然后作运算 a+b, 并将运算结果压入操作数栈 NUM_S) ,直到从运算符栈中弹出第一个左括号。(4)若运算符 W 为表达式结束符= ,循环操作(设先后弹出的操作数为 a、b
3、,再从运算符栈 OPR_S 中弹出一个运算符,比如为+,然后作运算 a+b, 并将运算结果压入操作数栈 NUM_S) ,直到运算符栈为空为止。此时,操作数栈栈顶元素即为表达式的值。=举例: 计算 3+(5-2*3)/4-2=(1) 开始栈为空,3 入栈,+入栈, (无条件入栈,5 入栈,-号优先级比(高,所以-号入栈,2 入栈,*优先级比目前栈顶的 -号优先级高,所以 *入栈,3 入栈,接着扫描到)括号, )括号不入栈| | | |- -| 3 | | * |- -| 2 | | - |- -| 5 | | ( |- -| 3 | | + |- -操作数栈 操作符栈(2) 在)括号碰到(括号之
4、前,让操作数栈一直出栈,直到让左括号出栈为止所以: 2,3 弹出操作数栈,*弹出操作符号栈,计算 2*3 = 6,然后将 6 入操作数栈| | | |- -| | | |- -| 6 | | - |- -| 5 | | ( |- -| 3 | | + |- -操作数栈 操作符栈(3) 接着 6,5 弹出操作数栈,-弹出操作符栈,计算 5-6 = -1, 然后将-1 入操作数栈,然后左括号出栈| | | |- -| | | |- -| | | |- -| -1 | | |- -| 3 | | + |- -操作数栈 操作符栈(4) 接着向下遍历表达式,到/号,优先级比操作符栈栈顶+高,所以/ 压栈
5、,然后接着扫描,4 入栈,再接着扫描到-号,优先级比操作符栈栈顶/的优先级低,则操作数栈4,-1 出栈,操作符栈/出栈,计算-1/4 = 0, | | | |- -| | | |- -| 4 | | |- -| -1 | | / |- -| 3 | | + |- -操作数栈 操作符栈(5) 将上一步结果 0 压入操作数栈,刚才扫描到的-号,优先级和+号相同,则- 号不入栈,将 0,3 弹出,将+号弹出,计算 3+0 = 3 | | | |- -| | | |- -| | | |- -| 0 | | |- -| 3 | | + |- -操作数栈 操作符栈(6) 将上一步中的结果 3 压入操作数栈,-号入操作符栈,接着扫描到 2,2 入操作数栈,接着扫描,发现到了=号,则操作数栈 2,3 弹出,操作符栈-号弹出,计算 3-2 = 1| | | |- -| | | |- -| | | |- -| 2 | | |- -| 3 | | - |- - 操作数栈 操作符栈(7) 将上一步中的结果 1 压入操作数栈,最后 1 弹出栈,作为最后结果。| | | |- -| | | |- -| | | |- -| | | |- -| 1 | | |- -操作数栈 操作符栈/= 完=/