我试图在课堂上理解一个关于使用堆栈和队列作为编程计算器的方法的主题。我了解什么是中缀和后缀表达式,但是它如何使程序更容易评估表达式以及为什么队列和堆栈在这种情况下是理想的?谢谢
问问题
7134 次
1 回答
4
它使操作顺序更易于处理,例如:
+ * - 4 2 5 3
只能表示
((4 - 2) * 5) + 3
这对我们来说可能更具可读性,但我们需要知道操作的顺序并匹配括号才能弄清楚。
至于实现:如果你有一个堆栈,你可以按如下方式处理上面的表达式:
- 读取
+
(操作),将其压入堆栈, - 读取
*
(操作),将其压入堆栈, - 读取
-
(操作),将其压入堆栈, - 读
4
(一个数字),栈顶不是数字,所以压入栈中。 - 读取
2
(一个数字),栈顶是一个数字,所以从栈中弹出两次,得到4 - 2
,计算(2
),将结果(2
)压入栈中。 - 读取
5
(一个数字),栈顶是一个数字,所以从栈中弹出两次,得到2 * 5
,将结果(10
)压入栈中。 - 读取
3
(一个数字),栈顶是一个数字,所以从栈中弹出两次,得到3 + 10
,将结果(13
)压入栈中。 - 没有什么可读取的,从堆栈中弹出并返回结果 (
13
)。
如您所见,表达式是使用一些简单的规则进行评估的,无需在整个字符串中搜索括号,也无需决定乘法是否优先于加法和减法。
于 2012-03-04T04:47:30.237 回答