Schrijf een programma om een ​​Infix-expressie naar een Postfix-vorm te converteren.

Infix-expressie: De uitdrukking van de vorm a-operator b (a + b), d.w.z. wanneer een operator zich tussen elk paar operanden bevindt.
Postfix-expressie: De uitdrukking van de vorm a b-operator (ab+), d.w.z. wanneer elk paar operanden wordt gevolgd door een operator.

Voorbeelden:

Invoer: A+B*C+D
Uitgang: ABC*+D+

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

Waarom een ​​postfix-weergave van de uitdrukking?

De compiler scant de uitdrukking van links naar rechts of van rechts naar links.
Beschouw de uitdrukking: a + b * c + d

• De compiler scant eerst de expressie om de expressie b * c te evalueren, en scant vervolgens opnieuw de expressie om er a aan toe te voegen.
• Het resultaat wordt vervolgens na een nieuwe scan toegevoegd aan d.

Het herhaaldelijk scannen maakt het zeer inefficiënt. Infix-expressies zijn gemakkelijk leesbaar en oplosbaar door mensen, terwijl de computer de operatoren en haakjes niet gemakkelijk kan onderscheiden. Het is dus beter om de expressie vóór de evaluatie naar de postfix- (of prefix)-vorm te converteren.

De overeenkomstige uitdrukking in postfix-vorm is abc*+d+ . De postfix-expressies kunnen eenvoudig worden geëvalueerd met behulp van een stapel.

Hoe converteer ik een Infix-expressie naar een Postfix-expressie?

Om de tussenvoegsel-expressie naar een postfix-expressie te converteren, gebruikt u de Hieronder staan ​​de stappen om het bovenstaande idee te implementeren:

1. Scan de infix-expressie van links naar rechts .

2. Hieronder staan ​​de stappen om het bovenstaande idee te implementeren:
   1. Als het gescande teken een operand is, plaatst u dit in de postfix-expressie.
   3. Hieronder staan ​​de stappen om het bovenstaande idee te implementeren:
      1. Doe anders het volgende
         • Als de prioriteit en associativiteit van de gescande operator groter zijn dan de prioriteit en associativiteit van de operator in de stapel [of de stapel is leeg of de stapel bevat een ‘ ( ‘ ] en duw het vervolgens in de stapel. [‘ ^ ‘operator is rechtsassociatief en andere operatoren zoals’ + ',' – ',' * ' En ' / ‘zijn links-associatief].
           • Controleer vooral of er sprake is van een situatie waarbij de operator bovenaan de stapel en de gescande operator beide ‘ ^ ‘. In deze toestand is de prioriteit van de gescande operator hoger vanwege de juiste associativiteit. Het wordt dus in de operatorstack geduwd.
           • In alle andere gevallen waarin de bovenkant van de operatorstapel hetzelfde is als die van de gescande operator, haalt u de operator uit de stapel vanwege linkse associativiteit, waardoor de gescande operator minder voorrang heeft.
         • Anders verwijder je alle operators van de stapel die groter of gelijk zijn aan voorrang dan die van de gescande operator.
           • Nadat u dat gedaan heeft, duwt u de gescande operator naar de stapel. (Als u tijdens het poppen haakjes tegenkomt, stop dan daar en duw de gescande operator in de stapel.)
      4. Hieronder staan ​​de stappen om het bovenstaande idee te implementeren:
         1. Als het gescande teken een ‘ ( ', duw het naar de stapel.
         5. Hieronder staan ​​de stappen om het bovenstaande idee te implementeren:
            1. Als het gescande teken een ‘ ) ’, knal de stapel open en voer deze uit totdat een ‘ ( ' wordt aangetroffen en verwijder beide haakjes.
            6. Hieronder staan ​​de stappen om het bovenstaande idee te implementeren:
               1. Herhaal de stappen 2-5 totdat de infix-expressie is gescand.
               7. Hieronder staan ​​de stappen om het bovenstaande idee te implementeren:

                  fibonacci-code java

                  1. Zodra het scannen is voltooid, knalt u de stapel uit en voegt u de operators toe aan de postfix-expressie totdat deze niet leeg is.
                  8. Hieronder staan ​​de stappen om het bovenstaande idee te implementeren:
                     1. Druk ten slotte de postfix-expressie af.

                     Hieronder staan ​​de stappen om het bovenstaande idee te implementeren:

                     1. Illustratie:

                     Hieronder staan ​​de stappen om het bovenstaande idee te implementeren:

                     1. Volg de onderstaande illustratie voor een beter begrip
                        Hieronder staan ​​de stappen om het bovenstaande idee te implementeren:

                        1. Beschouw de tussenvoegselexpressie exp = a+b*c+d
                           en de infix-expressie wordt gescand met behulp van de iterator i , die is geïnitialiseerd als ik = 0 .

                           1e stap: Hier i = 0 en exp[i] = ‘a’, d.w.z. een operand. Voeg dit dus toe aan de postfix-expressie. Daarom, achtervoegsel = een .

                           

                           Voeg ‘a’ toe in het achtervoegsel

                           2e stap: Hier i = 1 en exp[i] = ‘+’, d.w.z. een operator. Duw dit in de stapel. achtervoegsel = een En stapel = {+} .

                           

                           Druk op ‘+’ in de stapel

                           3e stap: Nu i = 2 en exp[i] = ‘b’, d.w.z. een operand. Voeg dit dus toe aan de postfix-expressie. achtervoegsel = ab En stapel = {+} .

                           

                           Voeg 'b' toe in het achtervoegsel

                           4e stap: Nu i = 3 en exp[i] = ‘*’, d.w.z. een operator. Duw dit in de stapel. achtervoegsel = ab En stapel = {+, *} .

                           

                           Druk op ‘*’ in de stapel

                           5e stap: Nu i = 4 en exp[i] = ‘c’, d.w.z. een operand. Voeg dit toe in de postfix-expressie. achtervoegsel = abc En stapel = {+, *} .

                           

                           Voeg ‘c’ toe in het achtervoegsel

                           6e stap: Nu i = 5 en exp[i] = ‘+’, d.w.z. een operator. Het bovenste element van de stapel heeft een hogere prioriteit. Dus knal totdat de stapel leeg raakt of het bovenste element minder prioriteit heeft. ‘*’ wordt uitgeklapt en toegevoegd in het postfix. Dus achtervoegsel = abc* En stapel = {+} .

                           

                           Pop ‘*’ en voeg een postfix toe

                           Het bovenste element is nu ‘ + ‘Ook dat heeft niet minder prioriteit. Pop het. achtervoegsel = abc*+ .

                           

                           Pop ‘+’ en voeg het toe als postfix

                           Nu is de stapel leeg. Dus duwen '+' in de stapel. stapel = {+} .

                           

                           Druk op ‘+’ in de stapel

                           7e stap: Nu i = 6 en exp[i] = ‘d’, d.w.z. een operand. Voeg dit toe in de postfix-expressie. achtervoegsel = abc*+d .

                           

                           Voeg ‘d’ toe in het achtervoegsel

                           Laatste stap: Nu is er geen enkel element meer over. Maak dus de stapel leeg en voeg deze toe aan de postfix-expressie. achtervoegsel = abc*+d+ .

                           

                           Pop ‘+’ en voeg het toe als postfix

                           Hieronder ziet u de implementatie van het bovenstaande 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>= 'een' && c<= 'z') || (c>= 'Een' && 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 && stapel[stackIndex] != '(') { resultaat[resultIndex++] = stapel[stackIndex--];  } stapelIndex--; // Pop '(' } // Als een operator anders wordt gescand { 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) { resultaat[resultIndex++] = stapel[stackIndex--];  } resultaat[resultaatIndex] = ' ';  printf('%s
                           ', resultaat); } // Stuurprogrammacode int main() { char exp[] = 'a+b*(c^d-e)^(f+g*h)-i';  // Functieaanroep infixToPostfix(exp);  retour 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();  Stackstapel = nieuwe stapel();  voor (int i = 0; ik< s.length(); i++) {  char c = s.charAt(i);  // If the scanned character is an operand, add it to the output string.  if ((c>= 'een' && c<= 'z') || (c>= 'Een' && 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 = nieuwe stapel();  Lijstresultaat = nieuwe lijst();  voor (int i = 0; ik< s.Length; i++)  {  char c = s[i];  // If the scanned character is an operand, add it to the output string.  if ((c>= 'een' && c<= 'z') || (c>= 'Een' && 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 && stapel.Peek() != '(') { resultaat.Add(stapel.Pop());  } stapel.Pop(); // Pop '(' } // Als een operator anders wordt gescand { 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) { resultaat.Toevoegen(stack.Pop());  } Console.WriteLine(string.Join('', resultaat));  } // Stuurprogrammacode static void Main() { string exp = 'a+b*(c^d-e)^(f+g*h)-i';  // Functieaanroep 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>= 'een' && c<= 'z') || (c>= 'Een' && 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;  tekenreeks resultaat;  voor (int i = 0; ik< s.length(); i++) {  char c = s[i];  // If the scanned character is  // an operand, add it to the output string.  if ((c>= 'een' && c<= 'z') || (c>= 'Een' && 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; }>

                           
                           Uitvoer

                           abcd^e-fgh*+^*+i->

                           Tijdcomplexiteit: O(N), waarbij N de grootte is van de tussenvoegselexpressie
                           Hulpruimte: O(N), waarbij N de grootte is van de tussenvoegselexpressie