这是在百度二面的一道算法题,考的是编译原理里面最基础的部分,当时脑子里没有这个概念,答错了,现在整理出来...
问题:实现一个字符串计算器,包含+、-、*、/ 四种操作;输入内容是一个字符串“ (2*(1+3)+8)/4 ”,要求得出计算结果。
解答思路:使用栈的方式来实现,将运算中的中缀表达式转化为后缀表达式再计算[注1]。
步骤:遍历字符串,建立数据栈和操作栈两个栈,依次从数据栈和操作栈中取值,完成计算。
例如:对于表达式 (2*(1+3)+8)/4
计算方式:
将(压入栈1
将2压入栈2
将*压入栈1
将1压入栈2
将+压入栈1
将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 - 这是后缀表达式
友情提示:垃圾评论一律封号...