为什么中缀转换为前缀时要反转字符串

Question

在将中缀转换为前缀的第一步中，有人可以用简单的术语解释为什么我们应该反转字符串吗？有没有其他转换方法？

Answer 1

是的，你是绝对正确的，如果你必须将中缀转换为前缀，那么你必须从右到左扫描字符串。

为什么不从左到右？

如果您从左到右扫描，那么您将需要了解字符串中的运算符。

示例1：

Infix  : 2+3
Prefix : +23

现在，当您将其从左转换为右时，您应该了解字符串中尚未出现的+。在这个特定的示例中，这看起来很简单，现在考虑下面给出的另一个示例。

示例2：

Infix  : 2+3*4/5-6*7
Prefix : -+2/*345*67

现在，如果您从左到右扫描，那么当您扫描字符串的第 0 个索引时，程序应该知道 - 这将出现在字符串的第 7 个索引中，这可能是一项繁忙的工作。

所以最安全的方法是从右向左扫描字符串。

Answer 2

在将中缀转换为前缀的第一步中，有人可以用简单的术语解释为什么我们应该反转字符串吗？

在没有说明您指的是哪种算法的情况下，您让我们猜测，但一个简单的猜测是：

1. 以相反的顺序（从右到左）读取前缀表达式
2. 如果符号是操作数，则将其压入堆栈。否则，如果符号是运算符，则从堆栈中弹出两个操作数，并通过连接两个操作数和它们之间的运算符来创建一个字符串： string = (operand1 + operand + operand2)
3. 并将结果字符串推回堆栈
4. 重复上述步骤，直到Prefix表达式结束。
5. 最后堆栈将只有 1 个字符串，即结果字符串

请注意，在步骤 2 中，操作数 1 是第一个被弹出的。

显然，为什么你不能从左到右读取字符串的原因在这个算法中是相当明显的：你读到的第一个是一个运算符，并且你不会有任何操作数要弹出。

该算法之所以有效，是因为它将其转换为后缀，并使用了将后缀转换为中缀的算法。 “有点”是因为在反转时，您不仅将运算符放在操作数后面，还反转了操作数的顺序（这就是为什么在步骤 2 中您将顶部操作数视为左侧操作数）。

有没有其他转换方法？

是的，因为上面的算法基本上是抽象地评估后缀表达式并将其表示为中缀。您可以直接使用前缀表达式执行相同的操作。

1. 输出左括号
2. 读取第一个标记，如果它是操作数，则输出它，我们就完成了。否则：
3. 转换输入前缀表达式（递归地使用此算法）
4. 输出令牌读入2
5. 转换输入前缀表达式（递归地使用此算法）
6. 输出右括号

Answer 3

这是伪代码：

start reading infix from left to right

if scannedElement is '('
    push scannedElement to operator stack

else if scannedElement is ')'
    while (operatorStack peek is not equal to "(")
            operator is equal to operator stack pop
            firstPopOperand is equal to operand stack pop
            secondPopOperand is equal to operand stack pop
            formedOperation = operator + secondPopOperand + firstPopOperand
            push formedOperation to operandStack
    pop from operator stack (this will be "(")

else if scannedElement is an operator
    if operatorStack is empty or operatorStack peek's precedence smaller than scannedElement precedence
        operatorStack.push scannedElement
    else
        while (operatorStack is not empty 
        and operatorStack peek's precedence bigger than or equal to scannedElement precedence)
            operator is equal to operator stack pop
            firstPopOperand is equal to operand stack pop
            secondPopOperand is equal to operand stack pop
            formedOperation = operator + secondPopOperand + firstPopOperand
            push formedOperation to operandStack
        push scannedElement to the operator stack

if scannedElement is an operand
   push the scannedElement to operandStack

after the infix string scanned
while (operatorStack is not empty)
        operator is equal to operator stack pop
        firstPopOperand is equal to operand stack pop
        secondPopOperand is equal to operand stack pop
        formedOperation = operator + secondPopOperand + firstPopOperand
        push formedOperation to operandStack

result is equal to operandStack peek