Skriv et program for å konvertere et Infix-uttrykk til Postfix-form.

Infiksuttrykk: Uttrykket for formen a operator b (a + b), dvs. når en operator er i mellom hvert par av operander.
Postfix-uttrykk: Uttrykket for formen a b-operator (ab+), dvs. Når hvert par med operander blir fulgt av en operator.

Eksempler:

Inndata: A + B * C + D
Produksjon: ABC*+D+

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

Hvorfor postfix-representasjon av uttrykket?

Kompilatoren skanner uttrykket enten fra venstre til høyre eller fra høyre til venstre.
Tenk på uttrykket: a + b * c + d

• Kompilatoren skanner først uttrykket for å evaluere uttrykket b * c, og skanner deretter uttrykket igjen for å legge til a til det.
• Resultatet legges så til d etter en ny skanning.

Den gjentatte skanningen gjør den svært ineffektiv. Infix-uttrykk er lett lesbare og løses av mennesker, mens datamaskinen ikke kan skille operatørene og parentesen lett, så det er bedre å konvertere uttrykket til postfix (eller prefiks)-form før evaluering.

Det tilsvarende uttrykket i postfix-form er abc*+d+ . Postfix-uttrykkene kan enkelt evalueres ved hjelp av en stabel.

Hvordan konvertere et Infix-uttrykk til et Postfix-uttrykk?

For å konvertere infix-uttrykk til postfix-uttrykk, bruk Nedenfor er trinnene for å implementere ideen ovenfor:

1. Skann infiksuttrykket fra venstre til høyre .

2. Nedenfor er trinnene for å implementere ideen ovenfor:
   1. Hvis det skannede tegnet er en operand, legg det inn i postfix-uttrykket.
   3. Nedenfor er trinnene for å implementere ideen ovenfor:
      1. Ellers gjør du følgende
         • Hvis forrangen og assosiativiteten til den skannede operatøren er større enn forrangen og assosiativiteten til operatoren i stabelen [eller stabelen er tom eller stabelen inneholder en ' ( ’ ], og skyv den deretter inn i stabelen. [' ^ 'operatør er rett assosiativ og andre operatører som' + ',' – ',' * 'og' / 'er venstreassosiative].
           • Se spesielt etter en tilstand der operatøren på toppen av stabelen og den skannede operatøren begge er ' ^ ‘. I denne tilstanden er forrangen til den skannede operatøren høyere på grunn av dens riktige assosiativitet. Så den vil bli skjøvet inn i operatørstabelen.
           • I alle de andre tilfellene når toppen av operatørstabelen er den samme som den skannede operatøren, skyver operatøren ut av stabelen på grunn av venstre assosiativitet som gjør at den skannede operatøren har mindre forrang.
         • Ellers, pop alle operatorene fra stabelen som er større enn eller lik i forrang enn den skannede operatoren.
           • Etter å ha gjort det, skyv den skannede operatøren til stabelen. (Hvis du støter på parentes mens du popper, stopp der og skyv den skannede operatøren inn i stabelen.)
      4. Nedenfor er trinnene for å implementere ideen ovenfor:
         1. Hvis det skannede tegnet er en ( ', skyv den til stabelen.
         5. Nedenfor er trinnene for å implementere ideen ovenfor:
            1. Hvis det skannede tegnet er en ) ', sprett stabelen og skriv den ut til en ( ' blir påtruffet, og forkast begge parentesene.
            6. Nedenfor er trinnene for å implementere ideen ovenfor:
               1. Gjenta trinnene 2-5 til infiksuttrykket er skannet.
               7. Nedenfor er trinnene for å implementere ideen ovenfor:

                  linkedlist og arraylist

                  1. Når skanningen er over, sprett stabelen og legg til operatorene i postfix-uttrykket til det ikke er tomt.
                  8. Nedenfor er trinnene for å implementere ideen ovenfor:
                     1. Skriv til slutt ut postfix-uttrykket.

                     Nedenfor er trinnene for å implementere ideen ovenfor:

                     1. Illustrasjon:

                     Nedenfor er trinnene for å implementere ideen ovenfor:

                     1. Følg illustrasjonen nedenfor for en bedre forståelse
                        Nedenfor er trinnene for å implementere ideen ovenfor:

                        1. Tenk på infiksuttrykket exp = a+b*c+d
                           og infiksuttrykket skannes ved hjelp av iteratoren Jeg , som er initialisert som i = 0 .

                           1. trinn: Her er i = 0 og exp[i] = 'a', dvs. en operand. Så legg til dette i postfix-uttrykket. Derfor, postfix = a .

                           

                           Legg til 'a' i postfixet

                           2. trinn: Her er i = 1 og exp[i] = '+', dvs. en operator. Skyv dette inn i stabelen. postfix = a og stabel = {+} .

                           

                           Trykk '+' i stabelen

                           3. trinn: Nå er i = 2 og exp[i] = 'b', dvs. en operand. Så legg til dette i postfix-uttrykket. postfix = ab og stabel = {+} .

                           

                           Legg til 'b' i postfixet

                           4. trinn: Nå er i = 3 og exp[i] = '*', dvs. en operator. Skyv dette inn i stabelen. postfix = ab og stabel = {+, *} .

                           

                           Trykk '*' i stabelen

                           5. trinn: Nå er i = 4 og exp[i] = 'c', dvs. en operand. Legg til dette i postfix-uttrykket. postfix = abc og stabel = {+, *} .

                           

                           Legg til 'c' i postfixet

                           6. trinn: Nå er i = 5 og exp[i] = '+', dvs. en operator. Det øverste elementet i stabelen har høyere prioritet. Så pop til stabelen blir tom eller toppelementet har mindre forrang. '*' er poppet og lagt til i postfix. Så postfix = abc* og stabel = {+} .

                           

                           Pop '*' og legg til i postfix

                           Nå er toppelementet ' + ' som heller ikke har mindre forrang. Pop den. postfix = abc*+ .

                           

                           Pop '+' og legg den til i postfix

                           Nå er stabelen tom. Så press '+' i stabelen. stabel = {+} .

                           

                           Trykk '+' i stabelen

                           7. trinn: Nå er i = 6 og exp[i] = 'd', dvs. en operand. Legg til dette i postfix-uttrykket. postfix = abc*+d .

                           

                           Legg til 'd' i postfixet

                           Siste trinn: Nå er det ikke noe element igjen. Så tøm stabelen og legg den til i postfix-uttrykket. postfix = abc*+d+ .

                           

                           Pop '+' og legg den til i postfix

                           Nedenfor er implementeringen av algoritmen ovenfor:

                           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 '(' } // Hvis en operator skannes 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--];  } resultat[resultatindeks] = ' ';  printf('%s
                           ', resultat); } // Driverkode int main() { char exp[] = 'a+b*(c^d-e)^(f+g*h)-i';  // Funksjonskall infixToPostfix(exp);  returner 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 stabel();  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)  {  Stackstabel = ny stabel();  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 skannes 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) { resultat.Add(stack.Pop());  } Console.WriteLine(string.Join('', resultat));  } // Driverkode statisk void Main() { string exp = 'a+b*(c^d-e)^(f+g*h)-i';  // Funksjonskall 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; }>

                           
                           Produksjon

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

                           Tidskompleksitet: O(N), der N er størrelsen på infiksuttrykket
                           Hjelpeplass: O(N), der N er størrelsen på infiksuttrykket