logo

TechCodeview

Konverter Infix-udtryk til Postfix-udtryk

Skriv et program til at konvertere et Infix-udtryk til Postfix-form.

Infix udtryk: Udtrykket af formen a operator b (a + b), dvs. når en operator er mellem hvert par af operander.
Postfix udtryk: Udtrykket af formen a b-operator (ab+), dvs. Når hvert par operander efterfølges af en operator.



Eksempler:

Input: A + B * C + D
Produktion: ABC*+D+

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



Hvorfor postfix repræsentation af udtrykket?

Compileren scanner udtrykket enten fra venstre mod højre eller fra højre mod venstre.
Overvej udtrykket: a + b * c + d

  • Compileren scanner først udtrykket for at evaluere udtrykket b * c, og scanner derefter udtrykket igen for at tilføje a til det.
  • Resultatet tilføjes derefter til d efter endnu en scanning.

Den gentagne scanning gør den meget ineffektiv. Infix-udtryk er let læselige og løselige af mennesker, hvorimod computeren ikke let kan differentiere operatorerne og parenteserne, så det er bedre at konvertere udtrykket til postfix (eller præfiks)-form før evaluering.

Det tilsvarende udtryk i postfix-form er abc*+d+ . Postfix-udtrykkene kan nemt evalueres ved hjælp af en stak.



Hvordan konverteres et Infix-udtryk til et Postfix-udtryk?

For at konvertere infix-udtryk til postfix-udtryk skal du bruge Nedenfor er trinene til at implementere ovenstående idé:

  1. Scan infix-udtrykket fra venstre mod højre .

  2. Nedenfor er trinene til at implementere ovenstående idé:

    1. Hvis det scannede tegn er en operand, skal du sætte det i postfix-udtrykket.
    2. Nedenfor er trinene til at implementere ovenstående idé:

      1. Ellers gør du følgende
        • Hvis den scannede operatørs forrang og associativitet er større end operatørens forrang og associativitet i stakken [eller stakken er tom, eller stakken indeholder en ' ( ’ ], skub den derefter i stakken. [' ^ 'operator er rigtig associativ og andre operatorer som' + ',' – ',' * 'og' / 'er venstre-associative].
          • Kontroller især for en tilstand, hvor operatøren øverst i stakken og den scannede operatør begge er ' ^ ’. I denne tilstand er den scannede operatørs forrang højere på grund af dens rette associativitet. Så den bliver skubbet ind i operatørstakken.
          • I alle de andre tilfælde, hvor toppen af ​​operatørstakken er den samme som den scannede operator, skal du skyde operatøren ud af stakken på grund af venstre associativitet, på grund af hvilken den scannede operator har mindre forrang.
        • Ellers pop alle operatorer fra stakken, som er større end eller lig med i forrang end den scannede operator.
          • Efter at have gjort det Skub den scannede operatør til stakken. (Hvis du støder på parenteser, mens du springer, så stop der og skub den scannede operator i stakken.)
      2. Nedenfor er trinene til at implementere ovenstående idé:

        1. Hvis det scannede tegn er et ' ( ’, skub den til stakken.
        2. Nedenfor er trinene til at implementere ovenstående idé:

          1. Hvis det scannede tegn er et ' ) ', pop stakken og udskriv den, indtil en ( ' er stødt på, og kasser begge parenteser.
          2. Nedenfor er trinene til at implementere ovenstående idé:

            1. Gentag trin 2-5 indtil infix-udtrykket er scannet.
            2. Nedenfor er trinene til at implementere ovenstående idé:

              java objekt lighed
              1. Når scanningen er overstået, pop stakken og tilføj operatorerne i postfix-udtrykket, indtil det ikke er tomt.
              2. Nedenfor er trinene til at implementere ovenstående idé:

                1. Udskriv til sidst postfix-udtrykket.

                  2. Nedenfor er trinene til at implementere ovenstående idé:

                  1. Illustration:

                  Nedenfor er trinene til at implementere ovenstående idé:

                  1. Følg nedenstående illustration for en bedre forståelse

                    Nedenfor er trinene til at implementere ovenstående idé:

                    1. Overvej infix-udtrykket exp = a+b*c+d
                      og infix-udtrykket scannes ved hjælp af iteratoren jeg , som er initialiseret som i = 0 .

                      1. trin: Her er i = 0 og exp[i] = 'a', dvs. en operand. Så tilføj dette i postfix-udtrykket. Derfor, postfix = en .

                      Tilføje

                      Tilføj 'a' i postfixet

                      2. trin: Her er i = 1 og exp[i] = '+', dvs. en operator. Skub dette ind i stakken. postfix = en og stak = {+} .

                      Skubbe

                      Tryk på '+' i stakken

                      3. trin: Nu er i = 2 og exp[i] = 'b', dvs. en operand. Så tilføj dette i postfix-udtrykket. postfix = ab og stak = {+} .

                      gfg

                      Tilføj 'b' i postfixet

                      4. trin: Nu er i = 3 og exp[i] = '*', dvs. en operator. Skub dette ind i stakken. postfix = ab og stak = {+, *} .

                      Skubbe

                      Skub '*' i stakken

                      5. trin: Nu er i = 4 og exp[i] = 'c', dvs. en operand. Tilføj dette i postfix-udtrykket. postfix = abc og stak = {+, *} .

                      Tilføje

                      Tilføj 'c' i postfixet

                      6. trin: Nu er i = 5 og exp[i] = '+', dvs. en operator. Det øverste element i stakken har højere forrang. Så pop indtil stakken bliver tom, eller det øverste element har mindre forrang. '*' er poppet og tilføjet i postfix. Så postfix = abc* og stak = {+} .

                      Pop

                      Pop '*' og tilføj i postfix

                      Nu er det øverste element ' + 'der har heller ikke mindre forrang. Pop det. postfix = abc*+ .

                      Pop

                      Pop '+' og tilføj det i postfix

                      Nu er stakken tom. Så skub '+' i stakken. stak = {+} .

                      Skubbe

                      Tryk på '+' i stakken

                      7. trin: Nu er i = 6 og exp[i] = 'd', dvs. en operand. Tilføj dette i postfix-udtrykket. postfix = abc*+d .

                      Tilføje

                      Tilføj 'd' i postfixet

                      Sidste trin: Nu er der intet element tilbage. Så tøm stakken og tilføj den i postfix-udtrykket. postfix = abc*+d+ .

                      Pop

                      Pop '+' og tilføj det i postfix

                      Nedenfor er implementeringen af ​​ovenstående algoritme:

                      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 '(' } // Hvis en operator scannes 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++] = stak[stackIndex--];  } resultat[resultatindeks] = ' ';  printf('%s
', resultat); } // Driverkode int main() { char exp[] = 'a+b*(c^d-e)^(f+g*h)-i';  // Funktionskald infixToPostfix(exp);  retur 0; }>
                      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();  Stackstak = ny stak();  for (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)  {  Stackstak = ny stak();  Listeresultat = ny liste();  for (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 '(' } // Hvis en operator scannes 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('', resultat));  } // Driverkode statisk void Main() { string exp = 'a+b*(c^d-e)^(f+g*h)-i';  // Funktionskald 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;  streng resultat;  for (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; }>
                      Produktion 
                      abcd^e-fgh*+^*+i->

                      Tidskompleksitet: O(N), hvor N er størrelsen af ​​infix-udtrykket
                      Hjælpeplads: O(N), hvor N er størrelsen af ​​infix-udtrykket