c++ - 后缀到中缀对话

Question

我无法解决从后缀到中缀的这个表达式。请帮我详细了解

5 x y - / x y + 3 ^ 7 / +

Answer 1

这不是代码，而是方式，您应该将后缀扩展为中缀::

5 xy - / xy + 3 ^ 7 / +

5 (xy) / xy+ 3^ 7 / +

(5/(xy)) xy+ 3^ 7 / +

(5/(xy)) (x+y)3^ 7 / +

(5/(xy)) ((x+y)^3) 7 / +

(5/(xy)) (((x+y)^3) / 7) +

(5/(xy)) + (((x+y)^3) / 7)

Answer 2

这很简单：

1. 您读取一个参数并决定它是一个值还是一个变量。如果是，则将参数压入堆栈。如果不是，那就是运营商。
2. 如果您有一个运算符，您将创建一个树，该树由作为根的运算符和与其子元素一样多的堆栈参数组成。您将树推入堆栈。
3. 当您想打印中缀表示法时，您可以按顺序遍历堆栈顶部（原始的后缀表示法只是同一棵树的后序遍历）。

为了在 C++ 中处理这个问题，我创建了一个基类 ( Expression)，派生类表示不同类型的节点 ( Value、Variable和BinaryOperation) 并维护一个std::stack<std::shared_ptr<Expression>>. 编写代码主要是一个打字练习。

Answer 3

后缀中缀：

5 x y - / x y + 3 ^ 7 / +

步

5 xy - /
A) 5xy-/ = 5 (xy)/ = (5 / (xy))
xy +
B) xy + = (x + y)
(x+y) 3 ^
B.1) (x + y ) 3 ^ = ((x + y) ^ 3 )
现在，(5 / (xy)) ((x + y) ^ 3 ) 7 / +
= (5 / (xy)) (((x + y) ^ 3 )/7 ) + = (5 / (xy)) + (((x + y) ^ 3 )/7 )

POSTFIX 和 PREFIX 是不使用括号的表达式。运算符的优先级是按照在表达式中出现的顺序决定的，因此评估表达式不需要搜索下一个操作来执行-FAST。

而在 INFIX 表达式中，运算符的优先级被括号覆盖。因此中缀表达式中有括号 - 需要搜索要执行的操作，例如 A+B%D - 因此SLOW。
这就是转换在计算机科学中有用的原因。