从中缀表达式转换为前缀表达式

Question

从中缀表达式转换为前缀表达式

17

我正在为一次考试做准备，但我不理解将中缀表达式转换为波兰表达式的方法，以下是表达式：

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

有人可以一步一步地说明如何将给定的表达式转换为前缀表达式吗？

- kar

14个回答

6

(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)))

- Caleb Hattingh

2

你的前缀输出似乎不正确。正确的应该是 */-abc-+de/fg - Rohit

5

如果你对中缀和前缀的含义有所不理解，我强烈建议你重新阅读你的教科书中相关章节。如果你只是为了解决这一个问题而得出正确答案，但仍然不理解这个概念，那么你并没有帮助到自己。

从算法角度来看，它非常简单。你只需要像计算机一样操作。首先，在每个计算周围加上括号，按照计算的顺序进行。然后（再次按照从第一个计算到最后一个的顺序），将运算符移动到其左侧表达式的前面。之后，你可以通过删除括号来简化表达式。

- T.E.D.

4

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

Step 1: (a-b)/c*(d+e- /fg)) 步骤1：(a-b)/c*(d+e- /fg)) Step 2: (a-b)/c*(+de - /fg) 步骤2：(a-b)/c*(+de - /fg) Step 3: (a-b)/c * -+de/fg 步骤3：(a-b)/c * -+de/fg Step 4: -ab/c * -+de/fg 步骤4：-ab/c * -+de/fg Step 5: /-abc * -+de/fg 步骤5：/-abc * -+de/fg Step 6: */-abc-+de/fg 步骤6：*/-abc-+de/fg 这是前缀表示法。

- Rahul Kumar Sharma

3

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

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

翻转它：

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

从左到右读取字符。
为运算符维护一个栈。

 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

- Rohit

1

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

记得从最左边到最右边扫描表达式从括号开始遵循“先来先服务”的规则... *，/，%处于同一级别且高于 +和-....所以 (a-b)=-bc前缀 (a-b)=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* 因此

(a-b)/c*(d + e – f / g) = -bc 前缀表达式 [-ab]/c*[-+de/fg] ---> 取自（1） / c * 暂不移动因为'/'和'*'在同一层级，所以'/'先于'*'，将'/'移到最右边：/[-ab]c * [-+de/fg] 然后将'*'移到最右边
- / [-ab]c[-+de/fg] = 移除分组符号 = */-abc-+de/fg --> 前缀表达式
(a-b)/c*(d + e – f / g) = bc- 后缀表达式 [ab-]/c*[de+fg/-]---> 取自（2）因为'/'和''在同一层级，所以'/'先于''，将'/'移到最左边：[ab-]c[de+fg/-]/ 然后将''移到最左边 [ab-] c [de+fg/-]/ = 移除分组符号= a b - c d e + f g / - / * --> 后缀表达式

- danny albay

0

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 ]

- Dyno Fu

0

前缀表达式中的操作符先于运算数：+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)

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

（注：此为编程相关内容）

                                 = * / - abc - + de / fg

前缀： * / - abc - + de / fg

- sdpshaw

0

这里有一个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));
    }
}

- Alireza Afzal Aghaei

0

使用堆栈将中缀表达式转换成后缀表达式：

     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

- user8459437

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rajdip · 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