Uzrakstiet programmu Infix izteiksmes konvertēšanai uz Postfix formu.

Infix izteiksme: Formas a operatora izteiksme b (a + b), t.i., kad operators atrodas starp katru operandu pāri.
Postfix izteiksme: Formas izteiksme a b operators (ab+), t.i., kad katram operandu pārim seko operators.

Piemēri:

Ievade: A+B*C+D
Izvade: ABC*+D+

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

Kāpēc izteiksmes attēlojums pēc fiksācijas?

Kompilators skenē izteiksmi no kreisās uz labo vai no labās uz kreiso.
Apsveriet izteicienu: a + b * c + d

• Kompilators vispirms skenē izteiksmi, lai novērtētu izteiksmi b * c, pēc tam vēlreiz skenē izteiksmi, lai tai pievienotu a.
• Rezultāts tiek pievienots d pēc citas skenēšanas.

Atkārtota skenēšana padara to ļoti neefektīvu. Infix izteiksmes cilvēkiem ir viegli salasāmas un atrisināmas, turpretim dators nevar viegli atšķirt operatorus un iekavas, tāpēc pirms novērtēšanas izteiksmi labāk pārvērst postfiksa (vai prefiksa) formā.

Atbilstošā izteiksme postfix formā ir abc*+d+ . Postfix izteiksmes var viegli novērtēt, izmantojot steku.

Kā pārveidot Infix izteiksmi par Postfix izteiksmi?

Lai pārveidotu infix izteiksmi par postfix izteiksmi, izmantojiet Tālāk ir norādītas darbības, lai īstenotu iepriekš minēto ideju:

1. Skenējiet infiksa izteiksmi no kreisās puses uz labo .

2. Tālāk ir norādītas darbības, lai īstenotu iepriekš minēto ideju:
   1. Ja skenētā rakstzīme ir operands, ievietojiet to postfix izteiksmē.
   3. Tālāk ir norādītas darbības, lai īstenotu iepriekš minēto ideju:
      1. Pretējā gadījumā rīkojieties šādi
         • Ja skenētā operatora prioritāte un asociativitāte ir lielāka nekā operatora prioritāte un asociativitāte kaudzē [vai steka ir tukša vai steka satur ' ( ‘ ], pēc tam iespiediet to kaudzē. [' ^ 'operators ir pareizi asociatīvs un citi operatori, piemēram,' + ',' – ',' * ' un ' / “ir kreisi asociatīvi].
           • Īpaši pārbaudiet stāvokli, kad operators kaudzes augšpusē un skenētais operators ir ' ^ ‘. Šajā stāvoklī skenētā operatora prioritāte ir augstāka, pateicoties tā pareizajai asociācijai. Tātad tas tiks iestumts operatora kaudzē.
           • Visos citos gadījumos, kad operatora steka augšdaļa ir tāda pati kā skenētais operators, tad izņemiet operatoru no steka kreisās asociativitātes dēļ, kuras dēļ skenētajam operatoram ir mazāka prioritāte.
         • Pretējā gadījumā izvelciet no steka visus operatorus, kuru prioritāte ir lielāka vai vienāda ar to, ko izmanto skenētais operators.
           • Pēc tam piespiediet skenēto operatoru uz kaudzīti. (Ja uznirstīšanas laikā redzat iekavas, apstājieties tur un iespiediet skenēto operatoru kaudzē.)
      4. Tālāk ir norādītas darbības, lai īstenotu iepriekš minēto ideju:
         1. Ja skenētā rakstzīme ir ' ( ', piespiediet to uz kaudzītes.
         5. Tālāk ir norādītas darbības, lai īstenotu iepriekš minēto ideju:
            1. Ja skenētā rakstzīme ir ' ) ”, izvelciet kaudzīti un izvadiet to līdz ( “, un atmetiet abas iekavas.
            6. Tālāk ir norādītas darbības, lai īstenotu iepriekš minēto ideju:
               1. Atkārtojiet darbības 2-5 līdz infiksa izteiksme tiek skenēta.
               7. Tālāk ir norādītas darbības, lai īstenotu iepriekš minēto ideju:

                  rakstzīmes uz virkni java

                  1. Kad skenēšana ir beigusies, izspiediet steku un pievienojiet operatorus postfix izteiksmei, līdz tā nav tukša.
                  8. Tālāk ir norādītas darbības, lai īstenotu iepriekš minēto ideju:
                     1. Visbeidzot izdrukājiet postfix izteiksmi.

                     Tālāk ir norādītas darbības, lai īstenotu iepriekš minēto ideju:

                     1. Ilustrācija:

                     Tālāk ir norādītas darbības, lai īstenotu iepriekš minēto ideju:

                     1. Izpildiet tālāk sniegto ilustrāciju, lai labāk izprastu
                        Tālāk ir norādītas darbības, lai īstenotu iepriekš minēto ideju:

                        1. Apsveriet infiksa izteiksmi exp = a+b*c+d
                           un infiksa izteiksme tiek skenēta, izmantojot iteratoru i , kas tiek inicializēts kā i = 0 .

                           1. solis: Šeit i = 0 un exp [i] = 'a', t.i., operands. Tāpēc pievienojiet to postfix izteiksmē. Tāpēc postfix = a .

                           

                           Pievienojiet 'a' postfix

                           2. solis: Šeit i = 1 un exp[i] = '+', t.i., operators. Ievietojiet to kaudzē. postfix = a un kaudze = {+} .

                           

                           Nospiediet “+” kaudzē

                           3. solis: Tagad i = 2 un exp [i] = 'b', t.i., operands. Tāpēc pievienojiet to postfix izteiksmē. postfix = ab un kaudze = {+} .

                           

                           Pievienojiet 'b' postfix

                           4. solis: Tagad i = 3 un exp[i] = '*', t.i., operators. Ievietojiet to kaudzē. postfix = ab un kaudze = {+, *} .

                           

                           Nospiediet “*” kaudzē

                           5. solis: Tagad i = 4 un exp[i] = 'c', t.i., operands. Pievienojiet to postfix izteiksmei. postfix = abc un kaudze = {+, *} .

                           

                           Pievienojiet 'c' postfix

                           6. solis: Tagad i = 5 un exp[i] = '+', t.i., operators. Augstākajam steka elementam ir augstāka prioritāte. Tāpēc spiediet, līdz kaudze kļūst tukša vai augšējam elementam ir mazāka prioritāte. “*” tiek izspiests un pievienots postfix. Tātad postfix = abc* un kaudze = {+} .

                           

                           Nospiediet “*” un pievienojiet postfix

                           Tagad augšējais elements ir ' + “, kam arī nav mazāka prioritāte. Uzlieciet to. postfix = abc*+ .

                           

                           Nospiediet “+” un pievienojiet to postfix

                           Tagad kaudze ir tukša. Tātad spiediet '+' kaudzē. kaudze = {+} .

                           

                           Nospiediet “+” kaudzē

                           7. solis: Tagad i = 6 un exp [i] = 'd', t.i., operands. Pievienojiet to postfix izteiksmei. postfix = abc*+d .

                           

                           Pievienojiet 'd' postfix

                           Pēdējais solis: Tagad nav palicis neviens elements. Tāpēc iztukšojiet kaudzi un pievienojiet to postfix izteiksmē. postfix = abc*+d+ .

                           

                           Nospiediet “+” un pievienojiet to postfix

                           Zemāk ir aprakstīta iepriekš minētā algoritma ieviešana:

                           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 && kaudze[stekaIndekss] != '(') { rezultāts[rezultāta indekss++] = steks[steckIndex--];  } stackIndex--; // Pop '(' } // Ja operators tiek skenēts 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) {rezultāts[rezultāta indekss++] = kaudze[steckIndex--];  } rezultāts[rezultāta rādītājs] = ' ';  printf('%s
                           ', rezultāts); } // Draivera kods int main() { char exp[] = 'a+b*(c^d-e)^(f+g*h)-i';  // Funkcijas izsaukums infixToPostfix(exp);  atgriezties 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();  Stackkaudze = new Stack();  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)  {  Stackkaudze = jauns kaudze();  Sarakstsrezultāts = jauns saraksts();  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 && kaudze.Peek() != '(') { rezultāts.Pievienot(steck.Pop());  } kaudze.Pop(); // Pop '(' } // Ja operators tiek skenēts else { while (steck.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) { rezultāts.Pievienot(steka.Pop());  } Console.WriteLine(string.Join('', rezultāts));  } // Draivera kods static void Main() { string exp = 'a+b*(c^d-e)^(f+g*h)-i';  // Funkcijas izsaukums 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;  stīgu rezultāts;  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; }>

                           
                           Izvade

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

                           Laika sarežģītība: O(N), kur N ir infiksa izteiksmes lielums
                           Palīgtelpa: O(N), kur N ir infiksa izteiksmes lielums