Scrieți un program pentru a converti o expresie Infix în formă Postfix.

Expresie infixă: Expresia formei a operatorului b (a + b), adică atunci când un operator se află între fiecare pereche de operanzi.
Expresie postfix: Expresia operatorului de formă a b (ab+), adică atunci când fiecare pereche de operanzi este urmată de un operator.

Exemple:

Intrare: A + B * C + D
Ieșire: ABC*+D+

Intrare: ((A + B) – C * (D / E)) + F
Ieșire: AB+CDE/*-F+

De ce reprezentarea postfixă a expresiei?

Compilatorul scanează expresia fie de la stânga la dreapta, fie de la dreapta la stânga.
Luați în considerare expresia: a + b * c + d

• Compilatorul scanează mai întâi expresia pentru a evalua expresia b * c, apoi scanează din nou expresia pentru a adăuga a la ea.
• Rezultatul este apoi adăugat la d după o altă scanare.

Scanarea repetată îl face foarte ineficient. Expresiile infixe sunt ușor de citit și de rezolvat de oameni, în timp ce computerul nu poate diferenția cu ușurință operatorii și parantezele, așa că este mai bine să convertiți expresia în formă postfix (sau prefix) înainte de evaluare.

Expresia corespunzătoare sub formă de postfix este abc*+d+ . Expresiile postfix pot fi evaluate cu ușurință folosind o stivă.

Cum se transformă o expresie Infix într-o expresie Postfix?

Pentru a converti expresia infixă în expresie postfixă, utilizați Mai jos sunt pașii pentru implementarea ideii de mai sus:

1. Scanați expresia infixă de la stanga la dreapta .

2. Mai jos sunt pașii pentru implementarea ideii de mai sus:
   1. Dacă caracterul scanat este un operand, puneți-l în expresia postfix.
   3. Mai jos sunt pașii pentru implementarea ideii de mai sus:
      1. În caz contrar, faceți următoarele
         • Dacă precedența și asociativitatea operatorului scanat sunt mai mari decât precedența și asociativitatea operatorului din stivă [sau stiva este goală sau stiva conține un „ ( ‘ ], apoi împingeți-l în stivă. [‘ ^ „operatorul are dreptate asociativ și alți operatori ca” + ',' – ',' * ' și ' / ‘ sunt asociative de stânga].
           • Verificați în special pentru o condiție în care operatorul din partea de sus a stivei și operatorul scanat sunt ambii „ ^ ‘. În această condiție, precedența operatorului scanat este mai mare datorită asociativității sale drepte. Deci va fi împins în stiva de operator.
           • În toate celelalte cazuri când partea de sus a stivei de operatori este aceeași cu operatorul scanat, apoi scoateți operatorul din stivă din cauza asociativității din stânga, datorită căreia operatorul scanat are mai puțină prioritate.
         • În caz contrar, scoateți toți operatorii din stivă care au prioritate mai mare sau egală cu cea a operatorului scanat.
           • După ce faceți asta, împingeți operatorul scanat în stivă. (Dacă întâlnești paranteze în timp ce popping, atunci opriți-vă acolo și împingeți operatorul scanat în stivă.)
      4. Mai jos sunt pașii pentru implementarea ideii de mai sus:
         1. Dacă caracterul scanat este un „ ( ', împinge-l în stivă.
         5. Mai jos sunt pașii pentru implementarea ideii de mai sus:
            1. Dacă caracterul scanat este un „ ) ’, deschideți stiva și scoateți-o până când apare un „ ( „ este întâlnit și eliminați ambele paranteze.
            6. Mai jos sunt pașii pentru implementarea ideii de mai sus:
               1. Repetați pașii 2-5 până când expresia infixă este scanată.
               7. Mai jos sunt pașii pentru implementarea ideii de mai sus:

                  centos vs rhel

                  1. Odată ce scanarea s-a încheiat, deschideți stiva și adăugați operatorii în expresia postfix până când nu este gol.
                  8. Mai jos sunt pașii pentru implementarea ideii de mai sus:
                     1. În cele din urmă, tipăriți expresia postfix.

                     Mai jos sunt pașii pentru implementarea ideii de mai sus:

                     1. Ilustrare:

                     Mai jos sunt pașii pentru implementarea ideii de mai sus:

                     1. Urmați ilustrația de mai jos pentru o mai bună înțelegere
                        Mai jos sunt pașii pentru implementarea ideii de mai sus:

                        1. Luați în considerare expresia infixă exp = a+b*c+d
                           iar expresia infixă este scanată folosind iteratorul i , care este inițializat ca i = 0 .

                           Pasul 1: Aici i = 0 și exp[i] = „a”, adică un operand. Deci, adăugați acest lucru în expresia postfix. Prin urmare, postfix = a .

                           

                           Adăugați „a” în postfix

                           Pasul 2: Aici i = 1 și exp[i] = „+”, adică un operator. Împingeți asta în stivă. postfix = a și stivă = {+} .

                           

                           Apăsați „+” în stivă

                           Pasul 3: Acum i = 2 și exp[i] = „b”, adică un operand. Așa că adăugați acest lucru în expresia postfix. postfix = ab și stivă = {+} .

                           

                           Adăugați „b” în postfix

                           Pasul 4: Acum i = 3 și exp[i] = ‘*’ adică un operator. Împingeți asta în stivă. postfix = ab și stivă = {+, *} .

                           

                           Apăsați „*” în stivă

                           Pasul 5: Acum i = 4 și exp[i] = „c”, adică un operand. Adăugați acest lucru în expresia postfix. postfix = abc și stivă = {+, *} .

                           

                           Adăugați „c” în postfix

                           Pasul 6: Acum i = 5 și exp[i] = „+”, adică un operator. Elementul cel mai de sus al stivei are o prioritate mai mare. Așa că pop până când stiva devine goală sau elementul de sus are mai puțină prioritate. „*” este afișat și adăugat în postfix. Asa de postfix = abc* și stivă = {+} .

                           

                           Apăsați „*” și adăugați în postfix

                           Acum elementul de top este „ + „De asemenea, asta nu are mai puțină prioritate. Pop it. postfix = abc*+ .

                           

                           Apăsați „+” și adăugați-l în postfix

                           Acum stiva este goală. Așa că împingeți '+' în stivă. stivă = {+} .

                           

                           Apăsați „+” în stivă

                           Pasul 7: Acum i = 6 și exp[i] = „d”, adică un operand. Adăugați acest lucru în expresia postfix. postfix = abc*+d .

                           

                           Adăugați „d” în postfix

                           Ultimul pas: Acum nu a mai rămas niciun element. Deci, goliți stiva și adăugați-o în expresia postfix. postfix = abc*+d+ .

                           

                           Apăsați „+” și adăugați-l în postfix

                           Mai jos este implementarea algoritmului de mai sus:

                           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] != '(') { rezultat[resultIndex++] = stack[stackIndex--];  } stackIndex--; // Pop '(' } // Dacă un operator este scanat 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) { rezultat[resultIndex++] = stivă[stackIndex--];  } rezultat[rezultatIndex] = ' ';  printf('%s
                           ', rezultat); } // Cod driver int main() { char exp[] = 'a+b*(c^d-e)^(f+g*h)-i';  // Apel de funcție infixToPostfix(exp);  întoarce 0; }>>>Javastivă = stivă nouă();  pentru (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);  } }>

                           Piton

                           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)  {  Stackstivă = stivă nouă();  Listărezultat = Listă nouă();  pentru (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() != '(') { rezultat.Add(stack.Pop());  } stack.Pop(); // Pop '(' } // Dacă un operator este scanat 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) { rezultat.Add(stack.Pop());  } Console.WriteLine(string.Join('', rezultat));  } // Cod driver static void Main() { string exp = 'a+b*(c^d-e)^(f+g*h)-i';  // Apel de funcție InfixToPostfix(exp);  } }>>>Javascript= '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) {  stackSf;  rezultat șir;  pentru (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; }>

                           
                           Ieșire

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

                           Complexitatea timpului: O(N), unde N este dimensiunea expresiei infixe
                           Spațiu auxiliar: O(N), unde N este dimensiunea expresiei infixe