logo

TechCodeview

Konvertieren Sie den Infix-Ausdruck in den Postfix-Ausdruck

Schreiben Sie ein Programm, um einen Infix-Ausdruck in ein Postfix-Format umzuwandeln.

Infix-Ausdruck: Der Ausdruck der Form a Operator b (a + b), d. h. wenn ein Operator zwischen jedem Operandenpaar steht.
Postfix-Ausdruck: Der Ausdruck hat die Form eines b-Operators (ab+), d. h. wenn auf jedes Operandenpaar ein Operator folgt.



Beispiele:

Eingang: A + B * C + D
Ausgabe: ABC*+D+

Eingang: ((A + B) – C * (D / E)) + F
Ausgabe: AB+CDE/*-F+



Warum Postfix-Darstellung des Ausdrucks?

Der Compiler durchsucht den Ausdruck entweder von links nach rechts oder von rechts nach links.
Betrachten Sie den Ausdruck: a + b * c + d

  • Der Compiler scannt zunächst den Ausdruck, um den Ausdruck b * c auszuwerten, und scannt dann den Ausdruck erneut, um a hinzuzufügen.
  • Das Ergebnis wird dann nach einem weiteren Scan zu d addiert.

Das wiederholte Scannen macht es sehr ineffizient. Infix-Ausdrücke sind für Menschen leicht lesbar und lösbar, wohingegen der Computer die Operatoren und Klammern nicht leicht unterscheiden kann. Daher ist es besser, den Ausdruck vor der Auswertung in die Postfix- (oder Präfix-)Form umzuwandeln.

Der entsprechende Ausdruck in Postfix-Form lautet abc*+d+ . Die Postfix-Ausdrücke können einfach über einen Stack ausgewertet werden.



Wie konvertiere ich einen Infix-Ausdruck in einen Postfix-Ausdruck?

Um einen Infix-Ausdruck in einen Postfix-Ausdruck zu konvertieren, verwenden Sie die Im Folgenden finden Sie die Schritte zur Umsetzung der oben genannten Idee:

  1. Scannen Sie den Infix-Ausdruck von links nach rechts .

  2. Im Folgenden finden Sie die Schritte zur Umsetzung der oben genannten Idee:

    1. Wenn das gescannte Zeichen ein Operand ist, fügen Sie es in den Postfix-Ausdruck ein.
    2. Im Folgenden finden Sie die Schritte zur Umsetzung der oben genannten Idee:

      1. Andernfalls gehen Sie wie folgt vor
        • Wenn die Priorität und Assoziativität des gescannten Operators größer sind als die Priorität und Assoziativität des Operators im Stapel [oder der Stapel leer ist oder der Stapel ein „ ( ‘ ], und schieben Sie es dann in den Stapel. [‘ ^ „Operator ist rechtsassoziativ und andere Operatoren wie“ + ',' – ',' * ' Und ' / ‘ sind linksassoziativ].
          • Überprüfen Sie insbesondere, ob ein Zustand vorliegt, bei dem sowohl der Bediener an der Spitze des Stapels als auch der gescannte Bediener „ ^ ‘. In diesem Zustand hat der gescannte Operator aufgrund seiner Rechtsassoziativität eine höhere Priorität. Es wird also in den Operator-Stack verschoben.
          • In allen anderen Fällen, in denen die Oberseite des Operatorstapels mit dem gescannten Operator übereinstimmt, entfernen Sie den Operator aufgrund der Linksassoziativität aus dem Stapel, wodurch der gescannte Operator weniger Vorrang hat.
        • Andernfalls entfernen Sie alle Operatoren aus dem Stapel, deren Priorität größer oder gleich der des gescannten Operators ist.
          • Danach schieben Sie den gescannten Bediener auf den Stapel. (Wenn Sie beim Öffnen auf eine Klammer stoßen, stoppen Sie dort und verschieben Sie den gescannten Operator in den Stapel.)
      2. Im Folgenden finden Sie die Schritte zur Umsetzung der oben genannten Idee:

        1. Wenn das gescannte Zeichen ein „ ( ‘, schiebe es auf den Stapel.
        2. Im Folgenden finden Sie die Schritte zur Umsetzung der oben genannten Idee:

          1. Wenn das gescannte Zeichen ein „ ) ', öffnen Sie den Stapel und geben Sie ihn aus, bis ein ' ( ' wird angetroffen, und verwerfen Sie beide Klammern.
          2. Im Folgenden finden Sie die Schritte zur Umsetzung der oben genannten Idee:

            1. Wiederholen Sie die Schritte 2-5 bis der Infix-Ausdruck gescannt wird.
            2. Im Folgenden finden Sie die Schritte zur Umsetzung der oben genannten Idee:

              Schakal gegen Wolf
              1. Sobald der Scanvorgang abgeschlossen ist, öffnen Sie den Stapel und fügen Sie die Operatoren im Postfix-Ausdruck hinzu, bis er nicht mehr leer ist.
              2. Im Folgenden finden Sie die Schritte zur Umsetzung der oben genannten Idee:

                1. Drucken Sie abschließend den Postfix-Ausdruck aus.

                  2. Im Folgenden finden Sie die Schritte zur Umsetzung der oben genannten Idee:

                  1. Illustration:

                  Im Folgenden finden Sie die Schritte zur Umsetzung der oben genannten Idee:

                  1. Befolgen Sie zum besseren Verständnis die folgende Abbildung

                    Im Folgenden finden Sie die Schritte zur Umsetzung der oben genannten Idee:

                    1. Betrachten Sie den Infix-Ausdruck exp = a+b*c+d
                      und der Infix-Ausdruck wird mit dem Iterator gescannt ich , die als initialisiert wird ich = 0 .

                      1. Schritt: Hier ist i = 0 und exp[i] = „a“, also ein Operand. Fügen Sie dies also in den Postfix-Ausdruck ein. Daher, Postfix = a .

                      Hinzufügen

                      Fügen Sie „a“ im Postfix hinzu

                      2. Schritt: Hier ist i = 1 und exp[i] = „+“, also ein Operator. Schieben Sie dies in den Stapel. Postfix = a Und Stapel = {+} .

                      Drücken

                      Drücken Sie „+“ im Stapel

                      3. Schritt: Jetzt ist i = 2 und exp[i] = ‚b‘, also ein Operand. Fügen Sie dies also in den Postfix-Ausdruck ein. Postfix = ab Und Stapel = {+} .

                      gfg

                      Fügen Sie „b“ im Postfix hinzu

                      4. Schritt: Jetzt ist i = 3 und exp[i] = ‚*‘, also ein Operator. Schieben Sie dies in den Stapel. Postfix = ab Und Stapel = {+, *} .

                      Drücken

                      Schieben Sie „*“ in den Stapel

                      5. Schritt: Jetzt ist i = 4 und exp[i] = ‚c‘, also ein Operand. Fügen Sie dies im Postfix-Ausdruck hinzu. Postfix = abc Und Stapel = {+, *} .

                      Hinzufügen

                      Fügen Sie „c“ im Postfix hinzu

                      6. Schritt: Jetzt ist i = 5 und exp[i] = „+“, also ein Operator. Das oberste Element des Stapels hat höhere Priorität. Pop also so lange, bis der Stapel leer ist oder das oberste Element weniger Vorrang hat. „*“ wird entfernt und im Postfix hinzugefügt. Also Postfix = abc* Und Stapel = {+} .

                      Pop

                      Geben Sie „*“ ein und fügen Sie das Postfix hinzu

                      Jetzt ist das oberste Element „ + „Das hat auch nicht weniger Vorrang.“ Pop es. Postfix = abc*+ .

                      Pop

                      Pop ‚+‘ und fügen Sie es im Postfix hinzu

                      Jetzt ist der Stapel leer. Also drängen '+' im Stapel. Stapel = {+} .

                      Drücken

                      Drücken Sie „+“ im Stapel

                      7. Schritt: Jetzt ist i = 6 und exp[i] = ‚d‘, also ein Operand. Fügen Sie dies im Postfix-Ausdruck hinzu. Postfix = abc*+d .

                      Hinzufügen

                      Fügen Sie „d“ im Postfix hinzu

                      Letzter Schritt: Jetzt ist kein Element mehr übrig. Leeren Sie also den Stapel und fügen Sie ihn in den Postfix-Ausdruck ein. Postfix = abc*+d+ .

                      Pop

                      Pop ‚+‘ und fügen Sie es im Postfix hinzu

                      Unten ist die Implementierung des obigen Algorithmus:

                      C 
                      #include  #include  #include  // Function to return precedence of operators int prec(char c)  c == '-')  return 1;  else  return -1;  // Function to return associativity of operators char associativity(char c) {  if (c == '^')  return 'R';  return 'L'; // Default to left-associative } // The main function to convert infix expression to postfix expression void infixToPostfix(char s[]) {  char result[1000];  int resultIndex = 0;  int len = strlen(s);  char stack[1000];  int stackIndex = -1;  for (int i = 0; i < len; i++) {  char c = s[i];  // If the scanned character is an operand, add it to the output string.  if ((c>= 'a' && c<= 'z') || (c>= 'A' && c<= 'Z') || (c>= '0' && c<= '9')) {  result[resultIndex++] = c;  }  // If the scanned character is an ‘(‘, push it to the stack.  else if (c == '(') {  stack[++stackIndex] = c;  }  // If the scanned character is an ‘)’, pop and add to the output string from the stack  // until an ‘(‘ is encountered.  else if (c == ')') {  while (stackIndex>= 0 && stack[stackIndex] != '(') { result[resultIndex++] = stack[stackIndex--];  } stackIndex--; // Pop '(' } // Wenn ein Operator gescannt wird else { while (stackIndex>= 0 && (prec(s[i])< prec(stack[stackIndex]) ||  prec(s[i]) == prec(stack[stackIndex]) &&  associativity(s[i]) == 'L')) {  result[resultIndex++] = stack[stackIndex--];  }  stack[++stackIndex] = c;  }  }  // Pop all the remaining elements from the stack  while (stackIndex>= 0) { result[resultIndex++] = stack[stackIndex--];  } result[resultIndex] = ' ';  printf('%s
', result); } // Treibercode int main() { char exp[] = 'a+b*(c^d-e)^(f+g*h)-i';  // Funktionsaufruf infixToPostfix(exp);  0 zurückgeben; }>
                      Java 
                      import java.util.Stack; public class InfixToPostfix {  // Function to return precedence of operators  static int prec(char c)   // Function to return associativity of operators  static char associativity(char c) {  if (c == '^')  return 'R';  return 'L'; // Default to left-associative  }  // The main function to convert infix expression to postfix expression  static void infixToPostfix(String s) {  StringBuilder result = new StringBuilder();  Stackstack = new Stack();  für (int i = 0; i< s.length(); i++) {  char c = s.charAt(i);  // If the scanned character is an operand, add it to the output string.  if ((c>= 'a' && c<= 'z') || (c>= 'A' && c<= 'Z') || (c>= '0' && c<= '9')) {  result.append(c);  }  // If the scanned character is an ‘(‘, push it to the stack.  else if (c == '(') {  stack.push(c);  }  // If the scanned character is an ‘)’, pop and add to the output string from the stack  // until an ‘(‘ is encountered.  else if (c == ')') {  while (!stack.isEmpty() && stack.peek() != '(') {  result.append(stack.pop());  }  stack.pop(); // Pop '('  }  // If an operator is scanned  else {  while (!stack.isEmpty() && (prec(s.charAt(i)) < prec(stack.peek()) ||  prec(s.charAt(i)) == prec(stack.peek()) &&  associativity(s.charAt(i)) == 'L')) {  result.append(stack.pop());  }  stack.push(c);  }  }  // Pop all the remaining elements from the stack  while (!stack.isEmpty()) {  result.append(stack.pop());  }  System.out.println(result);  }  // Driver code  public static void main(String[] args) {  String exp = 'a+b*(c^d-e)^(f+g*h)-i';  // Function call  infixToPostfix(exp);  } }>
                      Python 
                      def prec(c): if c == '^': return 3 elif c == '/' or c == '*': return 2 elif c == '+' or c == '-': return 1 else: return -1 def associativity(c): if c == '^': return 'R' return 'L' # Default to left-associative def infix_to_postfix(s): result = [] stack = [] for i in range(len(s)): c = s[i] # If the scanned character is an operand, add it to the output string. if ('a' <= c <= 'z') or ('A' <= c <= 'Z') or ('0' <= c <= '9'): result.append(c) # If the scanned character is an ‘(‘, push it to the stack. elif c == '(': stack.append(c) # If the scanned character is an ‘)’, pop and add to the output string from the stack # until an ‘(‘ is encountered. elif c == ')': while stack and stack[-1] != '(': result.append(stack.pop()) stack.pop() # Pop '(' # If an operator is scanned else: while stack and (prec(s[i]) < prec(stack[-1]) or (prec(s[i]) == prec(stack[-1]) and associativity(s[i]) == 'L')): result.append(stack.pop()) stack.append(c) # Pop all the remaining elements from the stack while stack: result.append(stack.pop()) print(''.join(result)) # Driver code exp = 'a+b*(c^d-e)^(f+g*h)-i' # Function call infix_to_postfix(exp)>
                      C# 
                      using System; using System.Collections.Generic; class Program {  // Function to return precedence of operators  static int Prec(char c)   c == '*')  return 2;  else if (c == '+'   // Function to return associativity of operators  static char Associativity(char c)  {  if (c == '^')  return 'R';  return 'L'; // Default to left-associative  }  // The main function to convert infix expression to postfix expression  static void InfixToPostfix(string s)  {  StackStapel = neuer Stapel();  AufführenErgebnis = neue Liste();  für (int i = 0; i< s.Length; i++)  {  char c = s[i];  // If the scanned character is an operand, add it to the output string.  if ((c>= 'a' && c<= 'z') || (c>= 'A' && c<= 'Z') || (c>= '0' && c<= '9'))  {  result.Add(c);  }  // If the scanned character is an ‘(‘, push it to the stack.  else if (c == '(')  {  stack.Push(c);  }  // If the scanned character is an ‘)’, pop and add to the output string from the stack  // until an ‘(‘ is encountered.  else if (c == ')')  {  while (stack.Count>0 && stack.Peek() != '(') { result.Add(stack.Pop());  } stack.Pop(); // Pop '(' } // Wenn ein Operator gescannt wird else { while (stack.Count> 0 && (Prec(s[i])< Prec(stack.Peek()) ||  Prec(s[i]) == Prec(stack.Peek()) &&  Associativity(s[i]) == 'L'))  {  result.Add(stack.Pop());  }  stack.Push(c);  }  }  // Pop all the remaining elements from the stack  while (stack.Count>0) { result.Add(stack.Pop());  } Console.WriteLine(string.Join('', result));  } // Treibercode static void Main() { string exp = 'a+b*(c^d-e)^(f+g*h)-i';  // Funktionsaufruf InfixToPostfix(exp);  } }>
                      Javascript 
                       /* Javascript implementation to convert  infix expression to postfix*/    //Function to return precedence of operators  function prec(c)  c == '-')  return 1;  else  return -1;    // The main function to convert infix expression  //to postfix expression  function infixToPostfix(s) {  let st = []; //For stack operations, we are using JavaScript built in stack  let result = '';  for(let i = 0; i < s.length; i++) {  let c = s[i];  // If the scanned character is  // an operand, add it to output string.  if((c>= 'a' && c<= 'z') || (c>= 'A' && c<= 'Z') || (c>= '0' && c<= '9'))  result += c;  // If the scanned character is an  // ‘(‘, push it to the stack.  else if(c == '(')  st.push('(');  // If the scanned character is an ‘)’,  // pop and to output string from the stack  // until an ‘(‘ is encountered.  else if(c == ')') {  while(st[st.length - 1] != '(')  {  result += st[st.length - 1];  st.pop();  }  st.pop();  }  //If an operator is scanned  else {  while(st.length != 0 && prec(s[i]) <= prec(st[st.length - 1])) {  result += st[st.length - 1];  st.pop();   }  st.push(c);  }  }  // Pop all the remaining elements from the stack  while(st.length != 0) {  result += st[st.length - 1];  st.pop();  }  console.log(result + '');  }    let exp = 'a+b*(c^d-e)^(f+g*h)-i';  infixToPostfix(exp); // This code is contributed by decode2207.>
                      C++14 
                      #include  using namespace std; // Function to return precedence of operators int prec(char c)  c == '*')  return 2;  else if (c == '+'  // Function to return associativity of operators char associativity(char c) {  if (c == '^')  return 'R';  return 'L'; // Default to left-associative } // The main function to convert infix expression // to postfix expression void infixToPostfix(string s) {  stackst;  String-Ergebnis;  für (int i = 0; i< s.length(); i++) {  char c = s[i];  // If the scanned character is  // an operand, add it to the output string.  if ((c>= 'a' && c<= 'z') || (c>= 'A' && c<= 'Z') || (c>= '0' && c<= '9'))  result += c;  // If the scanned character is an  // ‘(‘, push it to the stack.  else if (c == '(')  st.push('(');  // If the scanned character is an ‘)’,  // pop and add to the output string from the stack  // until an ‘(‘ is encountered.  else if (c == ')') {  while (st.top() != '(') {  result += st.top();  st.pop();  }  st.pop(); // Pop '('  }  // If an operator is scanned  else {  while (!st.empty() && prec(s[i]) < prec(st.top()) ||  !st.empty() && prec(s[i]) == prec(st.top()) &&  associativity(s[i]) == 'L') {  result += st.top();  st.pop();  }  st.push(c);  }  }  // Pop all the remaining elements from the stack  while (!st.empty()) {  result += st.top();  st.pop();  }  cout << result << endl; } // Driver code int main() {  string exp = 'a+b*(c^d-e)^(f+g*h)-i';  // Function call  infixToPostfix(exp);  return 0; }>
                      Ausgabe 
                      abcd^e-fgh*+^*+i->

                      Zeitkomplexität: O(N), wobei N die Größe des Infix-Ausdrucks ist
                      Hilfsraum: O(N), wobei N die Größe des Infix-Ausdrucks ist