Skriv ett program för att konvertera ett Infix-uttryck till Postfix-form.

Infix uttryck: Uttrycket för formen a operator b (a + b), dvs när en operator är mellan varje par av operander.
Postfix-uttryck: Uttrycket för formen a b-operator (ab+), dvs. När varje par operander följs av en operator.

Exempel:

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

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

Varför postfix representation av uttrycket?

Kompilatorn skannar uttrycket antingen från vänster till höger eller från höger till vänster.
Tänk på uttrycket: a + b * c + d

• Kompilatorn skannar först uttrycket för att utvärdera uttrycket b * c, sedan skannar uttrycket igen för att lägga till a till det.
• Resultatet läggs sedan till d efter ytterligare en skanning.

Den upprepade skanningen gör den mycket ineffektiv. Infix-uttryck är lätt läsbara och lösbara av människor, medan datorn inte enkelt kan skilja operatorerna och parenteserna åt, så det är bättre att konvertera uttrycket till postfix (eller prefix)-form innan utvärdering.

Motsvarande uttryck i postfix-form är abc*+d+ . Postfix-uttrycken kan enkelt utvärderas med hjälp av en stack.

Hur konverterar man ett Infix-uttryck till ett Postfix-uttryck?

För att konvertera infix-uttryck till postfix-uttryck, använd Nedan följer stegen för att implementera ovanstående idé:

1. Skanna infixuttrycket från vänster till höger .

2. Nedan följer stegen för att implementera ovanstående idé:
   1. Om det skannade tecknet är en operand, lägg det i postfix-uttrycket.
   3. Nedan följer stegen för att implementera ovanstående idé:
      1. Annars gör du följande
         • Om den skannade operatörens prioritet och associativitet är större än operatörens prioritet och associativitet i stacken [eller om stacken är tom eller om stacken innehåller en ' ( ’ ], tryck sedan in den i högen. [' ^ 'operatör är rätt associativ och andra operatorer som' + ',' – ',' * 'och' / ’ är vänsterassociativa].
           • Kontrollera särskilt för ett tillstånd när operatören överst i stapeln och den skannade operatören båda är ' ^ ’. I detta tillstånd är den skannade operatörens företräde högre på grund av dess rätta associativitet. Så den kommer att skjutas in i operatörsstapeln.
           • I alla andra fall när toppen av operatörsstacken är densamma som den skannade operatören, skjut sedan operatören från stacken på grund av vänsterassociativitet, vilket gör att den skannade operatören har mindre företräde.
         • Annars, poppa alla operatorer från stacken som är större än eller lika med företräde än den skannade operatorn.
           • Efter att ha gjort det Tryck den skannade operatören till stacken. (Om du stöter på parentes när du poppar, stanna där och tryck in den skannade operatorn i högen.)
      4. Nedan följer stegen för att implementera ovanstående idé:
         1. Om det skannade tecknet är ett ( ’, skjut den till traven.
         5. Nedan följer stegen för att implementera ovanstående idé:
            1. Om det skannade tecknet är ett ) ', poppa högen och mata ut den tills en ( ' påträffas och kassera båda parenteserna.
            6. Nedan följer stegen för att implementera ovanstående idé:
               1. Upprepa stegen 2-5 tills infixuttrycket skannas.
               7. Nedan följer stegen för att implementera ovanstående idé:

                  java boolesk sträng

                  1. När skanningen är över, poppa stacken och lägg till operatorerna i postfix-uttrycket tills det inte är tomt.
                  8. Nedan följer stegen för att implementera ovanstående idé:
                     1. Skriv till sist ut postfix-uttrycket.

                     Nedan följer stegen för att implementera ovanstående idé:

                     1. Illustration:

                     Nedan följer stegen för att implementera ovanstående idé:

                     1. Följ illustrationen nedan för en bättre förståelse
                        Nedan följer stegen för att implementera ovanstående idé:

                        1. Tänk på infixuttrycket exp = a+b*c+d
                           och infixuttrycket skannas med iteratorn i , som initieras som i = 0 .

                           1:a steget: Här är i = 0 och exp[i] = 'a', dvs en operand. Så lägg till detta i postfix-uttrycket. Därför, postfix = a .

                           

                           Lägg till 'a' i postfixet

                           Steg 2: Här är i = 1 och exp[i] = '+', dvs en operator. Skjut in detta i högen. postfix = a och stack = {+} .

                           

                           Tryck på '+' i högen

                           3:e steget: Nu är i = 2 och exp[i] = 'b', dvs en operand. Så lägg till detta i postfix-uttrycket. postfix = ab och stack = {+} .

                           

                           Lägg till 'b' i postfixet

                           Steg 4: Nu är i = 3 och exp[i] = '*', dvs en operator. Skjut in detta i högen. postfix = ab och stack = {+, *} .

                           

                           Tryck '*' i högen

                           Steg 5: Nu är i = 4 och exp[i] = 'c', dvs en operand. Lägg till detta i postfix-uttrycket. postfix = abc och stack = {+, *} .

                           

                           Lägg till 'c' i postfixet

                           6:e steget: Nu är i = 5 och exp[i] = '+', dvs en operator. Det översta elementet i stacken har högre prioritet. Så poppa tills stapeln blir tom eller det översta elementet har mindre företräde. '*' poppas och läggs till i postfix. Så postfix = abc* och stack = {+} .

                           

                           Poppa '*' och lägg till i postfix

                           Nu är toppelementet ' + ’ som inte heller har mindre företräde. Smäll den. postfix = abc*+ .

                           

                           Poppa '+' och lägg till det i postfix

                           Nu är stacken tom. Så tryck '+' i högen. stack = {+} .

                           

                           Tryck på '+' i högen

                           Steg 7: Nu är i = 6 och exp[i] = 'd', dvs en operand. Lägg till detta i postfix-uttrycket. postfix = abc*+d .

                           

                           Lägg till 'd' i postfixet

                           Sista steget: Nu finns inget element kvar. Så töm stacken och lägg till den i postfix-uttrycket. postfix = abc*+d+ .

                           

                           Poppa '+' och lägg till det i postfix

                           Nedan är implementeringen av ovanstående algoritm:

                           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] != '(') { resultat[resultIndex++] = stack[stackIndex--];  } stackIndex--; // Pop '(' } // Om en operator skannas 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) { resultat[resultIndex++] = stack[stackIndex--];  } resultat[resultIndex] = ' ';  printf('%s
                           ', resultat); } // Drivrutinskod int main() { char exp[] = 'a+b*(c^d-e)^(f+g*h)-i';  // Funktionsanrop infixToPostfix(exp);  returnera 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();  Stackstack = ny 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);  } }>

                           Pytonorm

                           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)  {  Stackstack = ny stack();  Listaresultat = ny lista();  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 '(' } // Om en operator skannas 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));  } // Driver code static void Main() { string exp = 'a+b*(c^d-e)^(f+g*h)-i';  // Funktionsanrop 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;  strängresultat;  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; }>

                           
                           Produktion

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

                           Tidskomplexitet: O(N), där N är storleken på infixuttrycket
                           Hjälputrymme: O(N), där N är storleken på infixuttrycket