输入一串字符串形如(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 - 这是后缀表达式





评论

更多老师:好文呀!如果早看这篇文章,面试就不会被刷下来了!
10月13日 00:47
一畔紫湖:感谢感谢!看完茅塞顿悟!
10月13日 00:57
10月13日 01:13
熊彼得:期待你的更新
10月13日 01:31
半盏:讲得很好吖,膜拜大佬
10月13日 05:23
单人青:受教了!非常感谢楼主!
10月13日 05:24
海山二:通俗易懂 贊
10月13日 05:37
江左猫郎:好文,特意来顶
10月13日 12:39
李献计:看起来不错~~
10月13日 14:14
乱码了:一直零零碎碎的看一些这方面的资料,都似懂非懂。这下全给整明白了。感谢!!!
10月13日 20:26

赞助商