输入一串字符串形如(2*(1+3)+8)/4 如何使用程序计算出结果 字符串输入计算器


这是在百度二面的一道算法题,考的是编译原理里面最基础的部分,当时脑子里没有这个概念,答错了,现在整理出来...

问题:实现一个字符串计算器,包含+、-、*、/ 四种操作;输入内容是一个字符串“ (2*(1+3)+8)/4 ”,要求得出计算结果。

解答思路:使用栈的方式来实现,将运算中的中缀表达式转化为后缀表达式再计算[注1]。

步骤:遍历字符串,建立数据栈和操作栈两个栈,依次从数据栈和操作栈中取值,完成计算。

例如:对于表达式 (2*(1+3)+8)/4 

计算方式:

  1. 将(压入栈1

  2. 将2压入栈2

  3. 将*压入栈1

  4. 将1压入栈2

  5. 将+压入栈1

  6. 将3压入栈2


此时,遇到 ) 

栈1中内容为 ( 、*、+ 

栈2中内容为2、1、3 

抛出栈1中的+,栈2中的1、3,运输1+3=4,然后将4压入栈2;

抛出并计算后

栈1中内容为 ( 、* 

栈2中内容为2、4 

继续....

懂了吧


*******************

注1:前缀、中缀、后缀表达式

三种表达式的记法,区别在于运算符相对于数据的位置,顾名思义,前缀表达式意思是运算符位于数据之前。

举例:

(3+4) * 5 - 6 这是中缀表达式

- * + 3 4 5 6 这是前缀表达式

3 4 + 5 * 6 - 这是后缀表达式



本文发表于2017年10月12日 17:10
阅读 2177 讨论 0 喜欢 0

讨论

周娱

君子和而不同
按照自己的方式,去度过人生

4181 1125794
抢先体验

扫码体验
趣味小程序
文字表情生成器

加入组织

扫码添加周娱微信
备注“加入组织”
邀请进开发群

闪念胶囊

人生是一场马拉松,起跑的优劣对于整段路途而言并没有那么重要,笑到最后的都是一直在跑的人,也就是一辈子都在学习的人。

角色是谁并不重要,重要的是会不会抢戏~

在这个世界上,最顶级的趋势叫时代。次一级的趋势才是经济周期,再往下是你所在的单位和公司的经营节奏。一个人赶不赶得上好时代得看运气,但要在好时代里不留下遗憾,得靠见识。

2009年,雷军40岁生日这天,他和几个朋友一起喝酒。雷军感慨,“人是不能推着石头往山上走的,这样会很累,而且会被山上随时滚落的石头给打下去。要做的是,先爬到山顶,随便踢块石头下去。”

离职要果断,入职要缓慢。

这一生,会遇到很多人,经历很多事,得到很多,也会失去很多。但无论如何,有两样东西,绝不能丢弃,一个叫良心,另一个叫理想。

数据结构和算法这个东西,如果你不去学,可能真的这辈子都用不到,也感受不到它的好。但是一旦掌握,你就会常常被它的强大威力所折服。之前你可能需要费很大劲儿来优化的代码,需要花很多心思来设计的架构,用了数据结构和算法之后,很容易就可以解决了。

人生路上,我们会遇到很多的坎。跨过去,你就可以成长,跨不过去就是困难和停滞。而在后面很长的一段时间里,你都需要为这个困难买单。

晚上在理发店烫了个头,本来想烫成陈奕迅的样子,但是最后成了黄渤 ( ̄﹏ ̄)~~~自行脑补

Copyright © 2016 - 2018 Cion.
All Rights Reserved.
备案:鲁ICP备16007319号.