conversion de l'infixe au préfixe

Je suis en train de préparer pour un examen où je ne pouvais pas comprendre la conversion de la notation infixe de polonais de notation ci-dessous expression:

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

Peut on dire étape par étape, comment l'expression donnée seront convertis en préfixe?

source d'informationauteur kar

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

5

Si il ya quelque chose à propos de ce préfixe, infixe et dire que vous n'avez pas tout à fait comprendre, je lui conseillerais de vous relire la section de votre manuel. Vous ne faites pas vous-même aucun faveurs si vous sortez de ce avec la bonne réponse pour ce problème, mais ne comprends toujours pas le concept.

Algorithme sage, son vachement simple. Vous suffit d'agir comme un ordinateur vous-même un peu. Commencez par ranger les parenthèses autour de chaque calcul dans l'ordre qu'il serait calculé. Ensuite (toujours dans l'optique de calcul du premier au dernier) il suffit de déplacer l'opérateur en face de l'expression sur son côté gauche. Après cela, vous pouvez simplifier en supprimant les parenthèses.
5

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

Préfixe notation polonaise inversée a l'opérateur dernier, il est difficile de savoir qui vous signifiait, mais le principe sera exactement le même):
1. (/f g)
2. (+ d e)
3. (- (+ d e) (/f g))
4. (- a b)
5. (/(- a b) c)
6. (* (/(- a b) c) (- (+ d e) (/f g)))
4
```
(a–b)/c*(d + e – f /g)
```
étape 1: (a-b)/c*(d+e- /fg))

étape 2: (a-b)/c*(+de - /fg)

étape 3: (a-b)/c * -+de/fg

Étape 4: -ab/c * -+de/fg

étape 5: /-abc * -+de/fg

étape 6: */-abc-+de/fg

C'est préfixe de notation.

J'ai vu cette méthode sur youtube donc de poster ici.

donné infix expression : (a–b)/c*(d + e – f /g)

inverse :

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

lire des caractères de gauche à droite.

maintenir une pile pour les opérateurs

 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.

crédits : youtube

1

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

souvenez-vous de la numérisation de l'expression de gauche à droite plus
démarrer sur les termes entre parenthèses
suivez le QUI VIENT d'ABORD à la règle...
*, /, % sont sur le même niveau et plus haut que
le + et le -.... donc
(a-b) = -bc préfixe
(a-b) = bc - pour postfix
un autre terme entre parenthèses:
(d + e - f /g) = faire déplacer le /premier
puis plus '+' avant moins soupir '-' (n'oubliez pas qu'ils sont sur le même niveau..)
(d + e - f /g)
déplacer /première
(d + e - (/fg)) = préfixe
(d + e - (fg/)) = postfix
suivi par + -
((+de) - (/fg)) = préfixe
((de+) - (fg/)) = postfix

(-(+de)(/fg)) = préfixe de sorte que la nouvelle expression est maintenant+de/fg (1)
((de+)(fg/)-) = postfix pour la nouvelle expression est aujourd'hui de+fg/- (2)

(a–b)/c* donc
1. (a-b)/c*(d + e – f /g) = -bc préfixe [ab]/c*[-+de/fg] ---> prises à partir de (1)
  /c * ne déplacez pas encore
  so '/' avant '*', parce qu'ils sur le même niveau, déplacez le '/'
  à droite de la barre : /[ab]c * [-+de/fg]
  puis déplacez - ' * ' à droite de la barre
  - /[ab]c[-+de/fg] = supprimer le regroupement des symboles = */-abc-+de/fg --> Préfixe
2. (a-b)/c*(d + e – f /g) = bc - pour postfix [ab]/c*[de+fg/-]---> prises à partir de (2)
  so '/' avant ' " parce qu'elles sur le même niveau, déplacez le '/'
  de gauche à droite: [ab]c[de+fg/-]/
  puis vous déplacer en " pour la gauche
  [ab] c [de+fg/-]/ = supprimer le regroupement des symboles= a b c d e + f g /- /* --> Postfix
0

simple recherche google est venu avec cette. Doute que quelqu'un peut expliquer ce soit plus simple. Mais je suppose qu'après une modification, je peux essayer de mettre de l'avant les notions de sorte que vous pouvez répondre à votre propre question.

Astuce :

Étude pour l'examen, dur, vous devez. Prévoir vous, le grade de prendre de la hauteur, je le fais 😀

Explication :

Il est tout au sujet de la façon dont les opérations sont associés avec des opérandes. chaque notation de type a ses propres règles. Vous avez juste besoin de casser et de se souvenir de ces règles. Si je vous disais que j'ai écrit (2*2)/3 [* /] (2,2,3) tout ce que vous devez faire est d'apprendre à tourner la dernière notation dans l'ancienne notation.

Mon custom de notation dit que prendre la première à deux opérandes et multiples, alors la résultante opérande doit être divisée par le troisième. Pour l'obtenir ? Ils essayent de vous apprendre trois choses.
1. Pour devenir à l'aise avec les différentes notations. L'exemple que j'ai donné est ce que vous trouverez dans l'assemblage de langues. opérandes (action) et des opérations (ce que vous voulez faire pour les opérandes).
2. Les règles de priorité dans le calcul n'est pas forcément nécessaire de suivre ceux trouvés dans les mathématiques.
3. D'évaluation: Comment une machine perçoit des programmes, et comment il peut les commander au moment de l'exécution.
0

Cet algorithme afin de vous aider à mieux comprendre .

L'étape 1. Push “)” sur la PILE, et d'ajouter “(“ à la fin de l'A.

L'étape 2. Le Scan d'Un de droite à gauche et répétez les étapes 3 à 6 pour chaque élément de A jusqu'à ce que la PILE est vide.

L'étape 3. Si un opérande est rencontré ajouter à B.

L'étape 4. Si une parenthèse fermante est rencontré push sur la PILE.

L'étape 5. Si un opérateur est rencontré alors:
un. À plusieurs reprises pop de la PILE et de l'ajouter à B chaque opérateur (sur le haut de la PILE) qui a la même
ou la priorité sur l'opérateur.
b. Ajouter de l'opérateur de PILE.

L'étape 6. Si parenthèse ouvrante est encontered alors
un. À plusieurs reprises pop à partir de la PILE et de l'ajouter à B (chaque opérateur sur le dessus de la pile jusqu'à ce qu'une parenthèse ouvrante est rencontrée)
b. Supprimer la parenthèse gauche.

L'étape 7. Sortie

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

La manœuvre de triage algorithme peut également être appliqués à la production de préfixe
la notation (aussi connu comme polish notation). Pour ce faire, on pourra simplement
commencer à partir de la fin d'une chaîne de tokens pour être analysé et travail
en arrière, l'inverse de la file d'attente de sortie (et donc de faire la file d'attente de sortie
une sortie de la pile), et retournez le à gauche et à droite de la parenthèse comportement
(se rappeler que la parenthèse gauche de comportement devrait pop jusqu'
il trouve une parenthèse droite).

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)

étape à travers:

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 ]

ici est une implémentation de java pour convertir infix pour le préfixe et d'évaluer préfixe expression (basé sur rajdip de l'algorithme)

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));
    }
}

0

En Préfixe opérateurs d'expression vient d'abord, puis opérandes : +ab[ oprator ab ]

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

Étape 1: (a - b) = (- ab) [ '(' a la plus haute priorité ]

étape 2: (d + e - f /g) = (d + e - /fg) [ '/' a la plus haute priorité ]
```
                       = (+ de - /fg )

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

                       = (- + de /fg)
```
Étape 3: (-ab )/c * (- + de /fg) = /- abc * (- + de /fg)
```
                                 = * /- abc - + de /fg 
```
Préfixe : * /- abc - + de /fg

Infix à PostFix, à l'aide de la Pile:

     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

-1

Peut-être que vous parlez de la La Notation Polonaise Inversée? Si oui, vous pouvez trouver sur wikipedia un très détaillées pas à pas exemple pour la conversion; si pas, je n'ai aucune idée de ce que vous demandez 🙁

Vous pouvez aussi lire ma réponse à une autre question à laquelle j'ai fourni une telle mise en œuvre: C++ opérations simples (+,-,/,*) évaluation de la classe
-2

C'est l'algorithme à l'aide de la pile.
Il suffit de suivre ces étapes simples.

1.Inverser la infix expression.

2.Remplacer '(' avec ')' et ')' avec '(' dans l'inversion de l'expression.

3.Maintenant appliquer la norme infix à postfix sous-routine.

4.Inverser le fondé de postfix expression, cela donnera préfixe requis expression.

Dans le cas où vous trouvez étape 3 difficile de consulter http://scanftree.com/Data_Structure/infix-to-prefix
lorsqu'un spécimen est également donnée.

Vous devez vous connecter pour publier un commentaire.