algorithm - 中缀到前缀的转换

Question

我正在准备考试，我无法理解以下表达式的中缀符号到波兰符号的转换：

(a–b)/c*(d + e – f / g)

谁能一步一步告诉给定的表达式将如何转换为前缀？

score 27 · Accepted Answer

Algorithm ConvertInfixtoPrefix

Purpose: Convert an infix expression into a prefix expression. Begin 
// Create operand and operator stacks as empty stacks. 
Create OperandStack
Create OperatorStack

// While input expression still remains, read and process the next token.

while( not an empty input expression ) read next token from the input expression

    // Test if token is an operand or operator 
    if ( token is an operand ) 
    // Push operand onto the operand stack. 
        OperandStack.Push (token)
    endif

    // If it is a left parentheses or operator of higher precedence than the last, or the stack is empty,
    else if ( token is '(' or OperatorStack.IsEmpty() or OperatorHierarchy(token) > OperatorHierarchy(OperatorStack.Top()) )
    // push it to the operator stack
        OperatorStack.Push ( token )
    endif

    else if( token is ')' ) 
    // Continue to pop operator and operand stacks, building 
    // prefix expressions until left parentheses is found. 
    // Each prefix expression is push back onto the operand 
    // stack as either a left or right operand for the next operator. 
        while( OperatorStack.Top() not equal '(' ) 
            OperatorStack.Pop(operator) 
            OperandStack.Pop(RightOperand) 
            OperandStack.Pop(LeftOperand) 
            operand = operator + LeftOperand + RightOperand 
            OperandStack.Push(operand) 
        endwhile

    // Pop the left parthenses from the operator stack. 
    OperatorStack.Pop(operator)
    endif

    else if( operator hierarchy of token is less than or equal to hierarchy of top of the operator stack )
    // Continue to pop operator and operand stack, building prefix 
    // expressions until the stack is empty or until an operator at 
    // the top of the operator stack has a lower hierarchy than that 
    // of the token. 
        while( !OperatorStack.IsEmpty() and OperatorHierarchy(token) lessThen Or Equal to OperatorHierarchy(OperatorStack.Top()) ) 
            OperatorStack.Pop(operator) 
            OperandStack.Pop(RightOperand) 
            OperandStack.Pop(LeftOperand) 
            operand = operator + LeftOperand + RightOperand 
            OperandStack.Push(operand)
        endwhile 
        // Push the lower precedence operator onto the stack 
        OperatorStack.Push(token)
    endif
endwhile 
// If the stack is not empty, continue to pop operator and operand stacks building 
// prefix expressions until the operator stack is empty. 
while( !OperatorStack.IsEmpty() ) OperatorStack.Pop(operator) 
    OperandStack.Pop(RightOperand) 
    OperandStack.Pop(LeftOperand) 
    operand = operator + LeftOperand + RightOperand

    OperandStack.Push(operand) 
endwhile

// Save the prefix expression at the top of the operand stack followed by popping // the operand stack.

print OperandStack.Top()

OperandStack.Pop()

End

score 6 · Accepted Answer

(a–b)/c*(d + e – f / g)

前缀表示法（反向波兰语最后有运算符，不清楚你指的是哪一个，但原理完全一样）：

(/ f g)
(+ d e)
(- (+ d e) (/ f g))
(- a b)
(/ (- a b) c)
(* (/ (- a b) c) (- (+ d e) (/ f g)))

score 5 · Accepted Answer

如果您不太了解中缀和前缀的含义，我强烈建议您重新阅读教科书的该部分。如果您从这个问题中得出正确的答案，那么您对自己没有任何帮助，但仍然不理解这个概念。

算法方面，它非常简单。你只是有点像一台电脑。首先按照计算的顺序在每个计算周围放置括号。然后（再次按照从第一个计算到最后一个计算的顺序）只需将运算符移动到表达式左侧的前面。之后，您可以通过删除括号来简化。

score 4 · Accepted Answer

(a–b)/c*(d + e – f / g)

步骤1：(a-b)/c*(d+e- /fg))

第2步：(a-b)/c*(+de - /fg)

第 3 步：(a-b)/c * -+de/fg

第4步：-ab/c * -+de/fg

第 5 步：/-abc * -+de/fg

第 6 步：*/-abc-+de/fg

这是前缀符号。

score 3 · Accepted Answer

我在 youtube 上看到了这种方法，因此在这里发布。

给定中缀表达式：(a–b)/c*(d + e – f / g)

扭转它：

)g/f-e+d(*c/)ba(

从左到右读取字符。
为操作员维护一个堆栈

 1. if character is operand add operand to the output
 2. else if character is operator or )
   2.1 while operator on top of the stack has lower or **equal** precedence than this character pop
   2.2 add the popped character to the output.
   push the character on stack

 3. else if character is parenthesis ( 
    3.1 [ same as 2 till you encounter ) . pop ) as well
 4. // no element left to read
   4.1 pop operators from stack till it is not empty
   4.2 add them to the output. 

reverse the output and print.

学分：YouTube

score 1 · Accepted Answer

(a–b)/c*(d + e – f / g)

请记住从最左到右扫描表达式最开始的括号项遵循 WHICH COMES FIRST 规则... *、/、% 处于同一级别并且高于 + 和 -...。所以 (ab) = -bc 前缀(ab) = bc- 后缀另一个括号中的术语： (d + e - f / g) = 先移动 /，然后加 '+' 在减号 '-' 之前先移动（记住它们处于同一水平.. ) (d + e - f / g) 移动 / 先 (d + e - (/fg)) = 前缀 (d + e - (fg/)) = 后缀后跟 + 然后 - ((+de) - (/ fg)) = 前缀 ((de+) - (fg/)) = 后缀

(-(+de)(/fg)) = 前缀，所以新表达式现在是 -+de/fg (1) ((de+)(fg/)-) = 后缀，所以新表达式现在是 de+fg/- (2)

(a–b)/c* 因此

(ab)/c*(d + e – f / g) = -bc 前缀 [-ab]/c*[-+de/fg] ---> 取自 (1) / c * 不要移动所以'/' 位于 '*' 之前，因为它们在同一级别，将 '/' 移动到最右边： /[-ab]c * [-+de/fg] 然后将 '*' 移动到最右边
- / [-ab]c[-+de/fg] = 去掉分组符号 = */-abc-+de/fg --> 前缀
(ab)/c*(d + e – f / g) = bc- 用于后缀 [ab-]/c*[de+fg/-]---> 取自 (2) 所以 '/' 先于' ' 因为它们在同一层级，所以把'/'移到最左边：[ab-]c [de+fg/-]/ 然后把' '移到最左边[ab-] c [de+fg/-]/ = 去掉分组符号= ab - cde + fg / - / * --> 后缀

score 0 · Accepted Answer

简单的谷歌搜索想出了这个。怀疑任何人都可以更简单地解释这一点。但我想在编辑之后，我可以尝试提出这些概念，以便您可以回答自己的问题。

暗示：

为考试而努力，你必须。预测你，成绩会变高，我愿意 :D

解释：

这完全是关于操作与操作数相关联的方式。每种符号类型都有自己的规则。你只需要分解并记住这些规则。如果我告诉你我将 (2*2)/3 写为 [* /] (2,2,3)，那么你需要做的就是学习如何将后一种表示法转换为前一种表示法。

我的自定义符号说，取前两个操作数并将它们相乘，然后得到的操作数应该除以第三个。得到它？他们试图教你三件事。

适应不同的符号。我给出的例子是你会在汇编语言中找到的。操作数（您对其进行操作）和操作（您想要对操作数执行的操作）。
计算中的优先规则不一定需要遵循数学中的优先规则。
评估：机器如何感知程序，以及它如何在运行时对它们进行排序。

score 0 · Accepted Answer

该算法将帮助您更好地理解。

步骤 1. 将“)”推入 STACK，并在 A 的末尾添加“(”。

步骤 2. 从右到左扫描 A，对 A 的每个元素重复步骤 3 到 6，直到 STACK 为空。

步骤 3. 如果遇到操作数，将其添加到 B。

第 4 步。如果遇到右括号，则将其推入堆栈。

步骤 5. 如果遇到操作员，则：重复从 STACK 中弹出并添加到 B 中（在 STACK 的顶部）具有与运算符相同或更高优先级的每个运算符。湾。将运算符添加到堆栈。

步骤 6. 如果遇到左括号，则 a。反复从堆栈中弹出并添加到 B（堆栈顶部的每个运算符，直到遇到左括号） b。删除左括号。

步骤 7. 退出

score 0 · Accepted Answer

这是一个将中缀转换为前缀并评估前缀表达式的java实现（基于rajdip的算法）

import java.util.*;

public class Expression {
    private static int isp(char token){
        switch (token){
            case '*':
            case '/':
                return 2;
            case '+':
            case '-':
                return 1;
            default:
                return -1;
        }
    }
    private static double calculate(double oprnd1,double oprnd2,char oprt){
        switch (oprt){
            case '+':
                return oprnd1+oprnd2;
            case '*':
                return oprnd1*oprnd2;
            case '/':
                return oprnd1/oprnd2;
            case '-':
                return oprnd1-oprnd2;
            default:
                return 0;
        }
    }
    public static String infix2prefix(String infix) {
        Stack<String> OperandStack = new Stack<>();
        Stack<Character> OperatorStack = new Stack<>();
        for(char token:infix.toCharArray()){
            if ('a' <= token && token <= 'z')
                OperandStack.push(String.valueOf(token));
            else if (token == '(' || OperatorStack.isEmpty() || isp(token) > isp(OperatorStack.peek()))
                OperatorStack.push(token);
            else if(token == ')'){
                while (OperatorStack.peek() != '(') {
                    Character operator = OperatorStack.pop();
                    String RightOperand = OperandStack.pop();
                    String LeftOperand = OperandStack.pop();
                    String operand = operator + LeftOperand + RightOperand;
                    OperandStack.push(operand);
                }
                OperatorStack.pop();
            }
            else if(isp(token) <= isp(OperatorStack.peek())){
                while (!OperatorStack.isEmpty() && isp(token)<= isp(OperatorStack.peek())) {
                    Character operator = OperatorStack.pop();
                    String RightOperand = OperandStack.pop();
                    String LeftOperand = OperandStack.pop();
                    String operand = operator + LeftOperand + RightOperand;
                    OperandStack.push(operand);
                }
                OperatorStack.push(token);
            }
        }
        while (!OperatorStack.isEmpty()){
            Character operator = OperatorStack.pop();
            String RightOperand = OperandStack.pop();
            String LeftOperand = OperandStack.pop();
            String operand = operator + LeftOperand + RightOperand;
            OperandStack.push(operand);
        }
        return OperandStack.pop();
    }
    public static double evaluatePrefix(String prefix, Map values){
        Stack<Double> stack = new Stack<>();
        prefix = new StringBuffer(prefix).reverse().toString();
        for (char token:prefix.toCharArray()){
            if ('a'<=token && token <= 'z')
                stack.push((double) values.get(token));
            else {
                double oprnd1 = stack.pop();
                double oprnd2 = stack.pop();
                stack.push(calculate(oprnd1,oprnd2,token));
            }
        }
        return stack.pop();
    }
    public static void main(String[] args) {
        Map dictionary = new HashMap<>();
        dictionary.put('a',2.);
        dictionary.put('b',3.);
        dictionary.put('c',2.);
        dictionary.put('d',5.);
        dictionary.put('e',16.);
        dictionary.put('f',4.);
        dictionary.put('g',7.);
        String s = "((a+b)/(c-d)+e)*f-g";
        System.out.println(evaluatePrefix(infix2prefix(s),dictionary));
    }
}

score 0 · Accepted Answer

https://en.wikipedia.org/wiki/Shunting-yard_algorithm

调车场算法也可用于产生前缀符号（也称为波兰符号）。要做到这一点，只需从要解析的一串标记的末尾开始并向后工作，反转输出队列（因此使输出队列成为输出堆栈），并翻转左右括号行为（记住现在-左括号行为应该弹出，直到找到现在的右括号）。

from collections import deque
def convertToPN(expression):
    precedence = {}
    precedence["*"] = precedence["/"] = 3
    precedence["+"] = precedence["-"] = 2
    precedence[")"] = 1

    stack  = []
    result = deque([])
    for token in expression[::-1]:
        if token == ')':
            stack.append(token)
        elif token == '(':
            while stack:
                t = stack.pop()
                if t == ")": break
                result.appendleft(t)
        elif token not in precedence:
            result.appendleft(token)
        else:
            # XXX: associativity should be considered here
            # https://en.wikipedia.org/wiki/Operator_associativity
            while stack and precedence[stack[-1]] > precedence[token]:
                result.appendleft(stack.pop())
            stack.append(token)

    while stack:
        result.appendleft(stack.pop())

    return list(result)

expression = "(a - b) / c * (d + e - f / g)".replace(" ", "")
convertToPN(expression)

一步一步：

step 1 : token ) ; stack:[ ) ]
result:[  ]
step 2 : token g ; stack:[ ) ]
result:[ g ]
step 3 : token / ; stack:[ ) / ]
result:[ g ]
step 4 : token f ; stack:[ ) / ]
result:[ f g ]
step 5 : token - ; stack:[ ) - ]
result:[ / f g ]
step 6 : token e ; stack:[ ) - ]
result:[ e / f g ]
step 7 : token + ; stack:[ ) - + ]
result:[ e / f g ]
step 8 : token d ; stack:[ ) - + ]
result:[ d e / f g ]
step 9 : token ( ; stack:[  ]
result:[ - + d e / f g ]
step 10 : token * ; stack:[ * ]
result:[ - + d e / f g ]
step 11 : token c ; stack:[ * ]
result:[ c - + d e / f g ]
step 12 : token / ; stack:[ * / ]
result:[ c - + d e / f g ]
step 13 : token ) ; stack:[ * / ) ]
result:[ c - + d e / f g ]
step 14 : token b ; stack:[ * / ) ]
result:[ b c - + d e / f g ]
step 15 : token - ; stack:[ * / ) - ]
result:[ b c - + d e / f g ]
step 16 : token a ; stack:[ * / ) - ]
result:[ a b c - + d e / f g ]
step 17 : token ( ; stack:[ * / ]
result:[ - a b c - + d e / f g ]

# the final while
step 18 : token ( ; stack:[  ]
result:[ * / - a b c - + d e / f g ]

score 0 · Accepted Answer

使用 Stack 对 PostFix 进行中缀：

     Example: Infix-->         P-Q*R^S/T+U *V
     Postfix -->      PQRS^*T/-UV

     Rules:
    Operand ---> Add it to postfix
    "(" ---> Push it on the stack
    ")" ---> Pop and add to postfix all operators till 1st left parenthesis
   Operator ---> Pop and add to postfix those operators that have preceded 
          greater than or equal to the precedence of scanned operator.
          Push the scanned symbol operator on the stack

score 0 · Accepted Answer

在前缀表达式中，运算符在前，然后是操作数：+ab[ 运算符 ab ]

中缀： (a–b)/c*(d + e – f / g)

第 1 步：(a - b) = (- ab)[ '(' 具有最高优先级 ]

第 2 步：(d + e - f / g) = (d + e - / fg)['/' 具有最高优先级]

                       = (+ de - / fg )

          ['+','-' has same priority but left to right associativity]

                       = (- + de / fg)

第 3 步：(-ab )/ c * (- + de / fg)=/ - abc * (- + de / fg)

                                 = * / - abc - + de / fg

字首： * / - abc - + de / fg

score -1 · Accepted Answer

也许您在谈论反向波兰表示法？如果是，您可以在 wikipedia 上找到一个非常详细的逐步转换示例；如果不是，我不知道你在问什么:(

您可能还想阅读我对提供此类实现的另一个问题的回答：C++ 简单操作 (+,-,/,*) 评估类

score -2 · Accepted Answer

这是使用堆栈的算法。
只需按照这些简单的步骤。

1.反转给定的中缀表达式。

2.在反向表达式中将'('替换为')'和')'替换为'('。3.

现在将标准中缀应用于后缀子例程。4.

反转建立的后缀表达式，这将给出所需的前缀表达式。

如果您会发现第 3 步很困难，请参阅http://scanftree.com/Data_Structure/infix-to-prefix ，其中还给出了一个已解决的示例。

algorithm - 中缀到前缀的转换

14 回答 14

Related

Reference