数据结构(四):栈的应用之表达式求值

1、表达式求值

问题描述:

用户从控制台输入一个数学表达式(所有输入均合法),数学表达式只包含四则运算,程序需输出表达式对应的结果,如:

输入:(1+2)*3+4-5

输出:8

解题思路:

涉及到的数学符号有 +、-、*、/、(、)。

因为左边的 + 比右边的 + 优先级要高,所以我们在判断符号优先级的时候还要带上方向。

带上方向的符号优先级表为(0表示相等,1表示左边比右边大,-1表示小):

横右竖左

+

-

*

/

+

1

1

-1

-1

-1

1

-

1

1

-1

-1

-1

1

*

1

1

1

1

-1

1

/

1

1

1

1

-1

1

-1

-1

-1

-1

0

0

1

1

1

1

0

0

两个相同优先级的符号总是左边的优先级比右边的高。

  1. 初始化两个栈,一个用来保存操作数,另一个用来保存操作符。
  2. 从控制台读取一个字符。
  3. 如果是操作数则压入操作数栈中。
  4. 如果是操作符,与操作符栈栈顶元素比较
  5. 若优先级高于栈顶元素,压入操作符栈
  6. 否则取出操作符栈栈顶元素和操作数栈栈顶的两个元素进行运算,并将运算结果压入操作数栈中。
  7. 继续执行第 4步
  8. 判断是否输入结束(遇到换行)
  9. 若输入结束,将操作符栈中的元素逐个弹出进行运算
  10. 否则继续第 2步
  11. 返回计算结果

代码请看:栈及其应用

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏星汉技术

原 荐 Scala的面向对象

----------目录--------------------------------------------------------- 1.Scala简介和...

30413
来自专栏函数式编程语言及工具

泛函编程(11)-延后计算-lazy evaluation

     延后计算(lazy evaluation)是指将一个表达式的值计算向后拖延直到这个表达式真正被使用的时候。在讨论lazy-evaluation之前...

2126
来自专栏星回的实验室

js重修课[四]:函数

函数有两种定义方法:定义表达式如var f = function(){};和声明语句如function f(){}。须知在变量提前这一现象中,声明语句可被提前,...

852
来自专栏计算机视觉

Python 函数使用记录,join函数和os.path.join用法

1.join()函数 语法:‘sep’.join(seq) 参数说明: sep:分隔符。可以为空 seq:要连接的元素序列、字符串、元组、字典等 上面的语法即:...

2777
来自专栏深度学习思考者

一文搞懂C/C++中指针那些事(上篇)

一 指针变量 1.间接存取        指针变量的值为地址;普通变量的值为数据;其中“*”为指针运算符。&是地址操作符,用来引用一个内存地址。通过在变量名...

20610
来自专栏我爱编程

Day10面向对象高级编程1/3

使用slots 正常情况下,当我们定义了一个class,创建了一个class的实例后,我们可以给该实例绑定任何属性和方法,这就是动态语言的灵活性。 class...

3255
来自专栏和蔼的张星的图像处理专栏

50. 数组剔除元素后的乘积两个遍历

给定一个整数数组A。 定义B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1], 计算B的时候请不要使用除法。...

1064
来自专栏有趣的Python和你

Python数据结构列表字典元组和集合

1196
来自专栏desperate633

LintCode 二进制中有多少个1题目分析

这种方法速度比较快,其运算次数与输入n的大小无关,只与n中1的个数有关。如果n的二进制表示中有k个1,那么这个方法只需要循环k次即可。其原理是不断清除n的二进制...

551
来自专栏前端知识分享

第164天:js方法调用的四种模式

函数名提升: script中脚本,在执行之前,会先把脚本中的所有的函数先进行编译解析,然后执行普通的js代码。

882

扫码关注云+社区