c++ - 在带有 '-(inner expression)' 的表达式周围添加括号

Question

我目前有一个标记中缀表达式的函数。

但是，我有 1 个小问题。

比如说我有:

2 ^ -(5 * 5)

这将转换为:

2
^
-1
*
(
5
*
5
)

然而，这并没有达到我想要的效果。

我的目标是将其括在括号中:

2
^
(
-1
*
(
5
*
5
)
)

这将完全按照我的需要进行评估。

我该怎么做才能得到这个输出。基于堆栈的方法很好。

鉴于我有一个如上所示的标记数组，我怎样才能得到一个包含在括号中的否定的新数组？

如有必要，我可以修改我的代码以生成以下不带 -1 * 的代码:

2
^
-
(
5
*
5
)

添加括号以便正确评估负数的算法是什么？

谢谢

Answer 1

如果您使用的是调车场算法，那么它并不难。首先要意识到，您正在处理两个不同的运算符，它们都使用“-”符号。一个是“减”运算符，一个是“取反”运算符。

诀窍在于如何区分它们。当您看到“-”时，请查看前面的符号。如果它为空(“-”在字符串的开头)、运算符或左括号，则它是取反运算符。否则就是减法。

每个运算符都有优先级和关联性，您必须提前知道这些才能实现调车场。减法运算符的优先级低于乘法和除法，并且是左结合的。取反的优先级介于乘法和指数之间，右结合。它也只需要 1 个操作数而不是 2 个。

所以你的表达式在转换后将是:2 5 5 * negate ^

好的，很好，但是如果“否定”不计算怎么办？没关系，弹出否定并将 -1 * 推到它的位置。现在你有 2 5 5 * -1 * ^。或者，如果您不计算负数，请将“-”替换为“0 1 -”以获得“2 5 5 * 0 1 - * ^”。