Подтвердить что ты не робот

Преобразование из инфикса в префикс

Я готовлю к экзамену, где я не мог понять преобразование нотации infix для нотации латинского текста для следующего выражения:

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

Может ли кто-нибудь сказать шаг за шагом, как данное выражение будет преобразовано в префикс?

4b9b3361

ОТВЕТЫ

Ответ 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

Ответ 2

Если есть что-то о том, что означает инфикс и префикс, что вы не совсем понимаете, я настоятельно рекомендую вам перечитать этот раздел вашего учебника. Вы не делаете себе никаких выгод, если вы выйдете из этого с правильным ответом на эту проблему, но до сих пор не понимаете концепцию.

Алгоритм-мудрый, его довольно прост. Вы просто играете как компьютер самостоятельно. Начните с установки парсеров вокруг каждого расчета в том порядке, в котором он будет рассчитан. Затем (опять по порядку от первого вычисления до последнего) просто переместите оператор перед выражением на левой стороне. После этого вы можете упростить, удалив парсеры.

Ответ 3

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

Ответ 4

(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

Это префиксная нотация.

Ответ 5

Я увидел этот метод на youtube, поэтому разместил здесь.

данное выражение infix: (a-b)/c * (d + e - f/g)

отмените его:

) г/е-е + d (* с /) б-а (

читать символы слева направо.
поддерживать один стек для операторов

 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

Ответ 6

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

помните, как сканировать выражение слева направо начать с заключенных в скобки терминов следуйте правилу WHICH COMES FIRST... *,/,% находятся на одном уровне и выше, чем + и -.... так (a-b) = -bc префикс (a-b) = bc- для постфикса другой заключенный в скобки термин: (d + e - f/g) = do переместить /first то плюс "+" наступает раньше минус вздох "-" (помните, что они на одном уровне..) (d + e - f/g) двигаться/сначала (d + e - (/fg)) = префикс (d + e - (fg/)) = postfix а затем + ((+ de) - (/fg)) = префикс ((de +) - (fg/)) = postfix

(- (+ de) (/fg)) = префикс, поэтому новое выражение теперь - + de/fg (1) ((de +) (fg/) -) = postfix, поэтому новое выражение теперь 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- для postfix [ab -]/c * [de + fg/-] --- > взято из (2) поэтому '/' идет первым до '', потому что они на одном уровне, переместите '/' влево: [ab-] c [de + fg/-]/ затем переместите '' в крайнее левое [ab-] c [de + fg/-]/= удалить символы группировки = a b - c d e + f g/-/* → Postfix

Ответ 7

простой поиск в Google придумал this. Сомневаюсь, что любой может объяснить это проще. Но я думаю, что после редактирования я могу попытаться выдвинуть концепции, чтобы вы могли ответить на собственный вопрос.

Подсказка:

Изучайте экзамен, усердно, вы должны. Прогнозируйте, класс становится высоким, я: D

Объяснение:

Это все о том, как операции связаны с операндами. каждый тип записи имеет свои собственные правила. Вам просто нужно сломать и запомнить эти правила. Если бы я сказал вам, что я написал (2 * 2)/3 как [*/] (2,2,3), все, что вам нужно сделать, это узнать, как превратить последнюю нотацию в прежнюю нотацию.

В моей пользовательской нотации указано, что первые два операнда и их несколько, тогда полученный операнд должен быть разделен на третье. Возьми? Они пытаются научить вас трем вещам.

  • Чтобы упроститься с разными обозначениями. Пример, который я дал, - это то, что вы найдете в языках ассемблера. операндов (которые вы действуете) и операций (что вы хотите сделать с операндами).
  • Приоритетные правила в вычислениях необязательно должны следовать за найденными в математике.
  • Оценка: как машина воспринимает программы и как она может их заказывать во время выполнения.

Ответ 8

Этот алгоритм поможет вам лучше понять.

Шаг 1. Нажмите ")" на STACK и добавьте "(" до конца A.

Шаг 2. Сканирование A справа налево и повторите шаги с 3 по 6 для каждого элемента A до тех пор, пока STACK не станет пустым.

Шаг 3. Если встречается операнд, добавьте его в B.

Шаг 4. Если встречается правая скобка, нажмите ее на STACK.

Шаг 5. Если встречается оператор, то:    а. Неоднократно выскакивают из STACK и добавляют к B каждого оператора (в верхней части STACK), который имеет одинаковый       или более высокий приоритет, чем оператор.    б. Добавьте оператора в STACK.

Шаг 6. Если левая скобка конкретизирована,    а. Неоднократно появляется из STACK и добавляется в B (каждый оператор поверх стека до тех пор, пока не встретится левая скобка)    б. Удалите левую скобку.

Шаг 7. Выход

Ответ 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 ]

Ответ 10

здесь реализована реализация java для преобразования infix в префикс и оценки префиксного выражения (на основе алгоритма 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));
    }
}

Ответ 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

Ответ 12

Infix to PostFix с помощью Stack:

     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

Ответ 13

Может быть, вы говорите о Reverse Polish Notation? Если да, вы можете найти в wikipedia очень подробный шаг за шагом для преобразования; если нет, я понятия не имею, о чем вы спрашиваете: (

Вы также можете прочитать мой ответ на другой вопрос, где я представил такую ​​реализацию: C++ простые операции (+, -,/, *) класс оценки

Ответ 14

Это алгоритм с использованием стека.
Просто выполните следующие простые шаги.

1. Исправить заданное выражение инфикса. 2. Замените '(' с ')' и ')' на '(' в обратном выражении.

3. Теперь примените стандартный инфикс к подпрограмме postfix.

4. Разверните основанное постфиксное выражение, это даст требуемое префиксное выражение.

Если вы находите шаг 3, проконсультируйтесь http://scanftree.com/Data_Structure/infix-to-prefix где также приведен пример разработки.