中缀到前缀的转换

Question

我正在准备一项考试，其中我无法理解以下表达式的中缀表示法到抛光表示法的转换：

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

任何人都可以逐步告诉如何将给定表达式转换为前缀吗？

Answer 1

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

Answer 2

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

前缀表示法（逆波兰操作符在最后，不清楚你指的是哪一个，但原理是完全相同的） ):

1. (/ fg)
2. (+ de)
3. (- (+ de) (/ fg))
4. (- ab)< /code>
5. (/ (- ab) c)
6. (* (/ (- ab) c) (- (+ de) (/ fg)))

Answer 3

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

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

Answer 4

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

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

步骤 2：(ab)/c*(+de - /fg)

步骤 3 ：(ab)/c * -+de/fg

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

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

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

这是前缀表示法。

Answer 5

我在 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

Answer 6

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

记住从最左边到最右边扫描表达式
从括号内的术语开始
遵循先到先得的规则...
*、/、% 处于同一水平并高于
+ 和 -...所以
(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* 因此

1. (ab)/c*(d + e – f /g) = -bc 前缀[-ab]/c*[-+de/fg] --->摘自（1）
   /c * 暂时不要动
   所以 '/' 首先出现在 '*' 之前，因为它们在同一级别，移动 '/'
   最右边：/[-ab]c * [-+de/fg]
   然后将“*”移动到最右边

   • / [-ab]c[-+de/fg] = 删除分组符号 = */-abc-+de/fg -->前缀

2. (ab)/c*(d + e – f / g) = bc- 后缀 [ab-]/c*[de+fg/-]--->摘自（2）
   所以 '/' 首先出现在 '' 之前，因为它们在同一级别，移动 '/'
   最左边：[ab-]c[de+fg/-]/
   然后将“”移动到最左边
   [ab-] c [de+fg/-]/ = 删除分组符号= ab - cde + fg / - / * -->后缀

Answer 7

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

提示：

为了考试而学习，你必须努力。预测你，成绩会变高，我会的：D

解释：

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

我的自定义表示法表示，将前两个操作数相乘，然后将所得操作数除以第三个操作数。得到它 ？他们试图教你三件事。

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

Answer 8

这个算法将帮助你更好地理解。

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

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

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

步骤 4。 如果遇到右括号，则将其推入 STACK

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

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

步骤 7. 退出

Answer 9

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 ]

Answer 10

这是一个用于将中缀转换为前缀并评估前缀表达式的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));
    }
}

Answer 11

在前缀表达式中，首先是运算符，然后是操作数： +ab[ oprator 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

Answer 12

使用堆栈对 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

Answer 13

也许您正在谈论逆波兰表示法？如果是，您可以在维基百科上找到非常详细的转换步骤示例；如果不是，我不知道你在问什么:(

你可能还想阅读我对另一个问题的回答，我在其中提供了这样的实现：C++ 简单操作（+、-、/、*）评估类

Answer 14

这是使用堆栈的算法。
只需遵循这些简单的步骤即可。

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

2.将反转表达式中的“(”替换为“)”，将“)”替换为“(”。

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

4.将建立的后缀表达式反转，得到所需的前缀表达式。

如果您发现第 3 步有困难，请参阅 http://scanftree.com/Data_Structure/infix-to-prefix
其中还给出了一个可行的例子。