logo

TechCodeview

Konvertuoti Infix išraišką į Postfix išraišką

Parašykite programą, skirtą Infix išraiškai konvertuoti į Postfix formą.

Infix išraiška: Formos a operatorius b (a + b) išraiška, ty kai operatorius yra tarp kiekvienos operandų poros.
Postfix išraiška: Formos a b operatoriaus išraiška (ab+), ty kai po kiekvienos operandų poros seka operatorius.



Pavyzdžiai:

Įvestis: A + B * C + D
Išvestis: ABC*+D+

Įvestis: ((A + B) – C * (D / E)) + F
Išvestis: AB+CDE/*-F+



Kodėl išraiškos atvaizdavimas postfix?

Kompiliatorius nuskaito išraišką iš kairės į dešinę arba iš dešinės į kairę.
Apsvarstykite išraišką: a + b * c + d

  • Kompiliatorius pirmiausia nuskaito išraišką, kad įvertintų išraišką b * c, tada vėl nuskaito išraišką, kad pridėtų prie jos a.
  • Tada rezultatas po kito nuskaitymo pridedamas prie d.

Pakartotinis nuskaitymas daro jį labai neveiksmingą. Infikso išraiškos yra lengvai skaitomos ir išsprendžiamos žmonėms, tuo tarpu kompiuteris negali lengvai atskirti operatorių ir skliaustų, todėl prieš vertinimą geriau konvertuoti išraišką į postfikso (arba priešdėlio) formą.

Atitinkama išraiška postfix forma yra abc*+d+ . Postfix išraiškas galima lengvai įvertinti naudojant krūvą.



Kaip konvertuoti Infix išraišką į Postfix išraišką?

Norėdami konvertuoti infikso išraišką į postfix išraišką, naudokite Toliau pateikiami žingsniai, kaip įgyvendinti aukščiau pateiktą idėją:

  1. Nuskaitykite infikso išraišką iš kairės į dešinę .

  2. Toliau pateikiami žingsniai, kaip įgyvendinti aukščiau pateiktą idėją:

    1. Jei nuskaitytas simbolis yra operandas, įdėkite jį į postfix išraišką.
    2. Toliau pateikiami žingsniai, kaip įgyvendinti aukščiau pateiktą idėją:

      1. Kitu atveju atlikite šiuos veiksmus
        • Jei nuskaityto operatoriaus pirmenybė ir asociatyvumas yra didesni nei operatoriaus pirmenybė ir asociatyvumas krūvoje [arba krūva tuščia arba jame yra „ ( ‘ ], tada įstumkite jį į krūvą. [' ^ 'operatorius yra teisingas asociatyvus ir kiti operatoriai, tokie kaip' + ',' – ',' * 'ir' / ‘yra kairieji asociatyvūs].
          • Ypač patikrinkite būseną, kai operatorius krūvos viršuje ir nuskaitytas operatorius yra „ ^ ‘. Esant tokiai sąlygai, nuskaityto operatoriaus pirmenybė yra didesnė dėl jo teisingo asociatyvumo. Taigi jis bus įstumtas į operatoriaus krūvą.
          • Visais kitais atvejais, kai operatorių krūvos viršus yra toks pat, kaip ir nuskaitytas operatorius, tada pašalinkite operatorių iš krūvos dėl kairiojo asociatyvumo, dėl kurio nuskaitytas operatorius turi mažesnę pirmenybę.
        • Kitu atveju iš dėklo iškelkite visus operatorius, kurių prioritetas yra didesnis arba lygus nuskaitytam operatoriui.
          • Tai atlikę, nuskaitytą operatorių stumkite į krūvą. (Jei iššokant matote skliaustus, sustokite ir įstumkite nuskaitytą operatorių į krūvą.)
      2. Toliau pateikiami žingsniai, kaip įgyvendinti aukščiau pateiktą idėją:

        1. Jei nuskaitytas simbolis yra „ ( “, stumkite jį į krūvą.
        2. Toliau pateikiami žingsniai, kaip įgyvendinti aukščiau pateiktą idėją:

          1. Jei nuskaitytas simbolis yra „ ) “, išmeskite krūvą ir išveskite iki „ ( “, ir atmeskite abu skliaustus.
          2. Toliau pateikiami žingsniai, kaip įgyvendinti aukščiau pateiktą idėją:

            1. Pakartokite veiksmus 2-5 kol bus nuskaityta infikso išraiška.
            2. Toliau pateikiami žingsniai, kaip įgyvendinti aukščiau pateiktą idėją:

              spyruokliniai batai
              1. Kai nuskaitymas baigsis, iškelkite krūvą ir pridėkite operatorius į postfix išraišką, kol ji nebus tuščia.
              2. Toliau pateikiami žingsniai, kaip įgyvendinti aukščiau pateiktą idėją:

                1. Galiausiai išspausdinkite postfix išraišką.

                  2. Toliau pateikiami žingsniai, kaip įgyvendinti aukščiau pateiktą idėją:

                  1. Iliustracija:

                  Toliau pateikiami žingsniai, kaip įgyvendinti aukščiau pateiktą idėją:

                  1. Norėdami geriau suprasti, vadovaukitės toliau pateikta iliustracijomis

                    Toliau pateikiami žingsniai, kaip įgyvendinti aukščiau pateiktą idėją:

                    1. Apsvarstykite infikso išraišką exp = a+b*c+d
                      o infikso išraiška nuskaitoma naudojant iteratorių i , kuris inicijuojamas kaip i = 0 .

                      1 žingsnis: Čia i = 0 ir exp [i] = 'a', ty operandas. Taigi pridėkite tai į postfix išraišką. Todėl, postfix = a .

                      Papildyti

                      Pridėkite „a“ prie postfix

                      2 žingsnis: Čia i = 1 ir exp[i] = '+', ty operatorius. Įstumkite tai į krūvą. postfix = a ir krūva = {+} .

                      Stumti

                      Paspauskite „+“ krūvoje

                      3 žingsnis: Dabar i = 2 ir exp [i] = 'b', ty operandas. Taigi pridėkite tai į postfix išraišką. postfix = ab ir krūva = {+} .

                      gfg

                      Pridėkite „b“ prie postfix

                      4 žingsnis: Dabar i = 3 ir exp[i] = '*', ty operatorius. Įstumkite tai į krūvą. postfix = ab ir krūva = {+, *} .

                      Stumti

                      Paspauskite „*“ krūvoje

                      5 žingsnis: Dabar i = 4 ir exp [i] = 'c', ty operandas. Įtraukite tai į postfix išraišką. postfix = abc ir krūva = {+, *} .

                      Papildyti

                      Į postfix pridėkite „c“.

                      6 žingsnis: Dabar i = 5 ir exp[i] = '+', ty operatorius. Viršutinis krūvos elementas turi didesnę pirmenybę. Taigi stumkite tol, kol krūva taps tuščia arba viršutinis elementas turės mažiau pirmenybės. „*“ yra iššokęs ir įtrauktas į postfix. Taigi postfix = abc* ir krūva = {+} .

                      Pop

                      Pažymėkite „*“ ir pridėkite postfix

                      Dabar viršutinis elementas yra ' + “, kuris taip pat turi ne mažesnę pirmenybę. Pakelkite. postfix = abc*+ .

                      Pop

                      Pažymėkite „+“ ir pridėkite jį prie postfix

                      Dabar krūva tuščia. Taigi stumkite '+' rietuvėje. krūva = {+} .

                      Stumti

                      Paspauskite „+“ krūvoje

                      7 žingsnis: Dabar i = 6 ir exp [i] = 'd', ty operandas. Įtraukite tai į postfix išraišką. postfix = abc*+d .

                      Papildyti

                      Į postfix pridėkite „d“.

                      Paskutinis žingsnis: Dabar neliko elemento. Taigi ištuštinkite krūvą ir įtraukite ją į postfix išraišką. postfix = abc*+d+ .

                      Pop

                      Pažymėkite „+“ ir pridėkite jį prie postfix

                      Žemiau pateikiamas aukščiau pateikto algoritmo įgyvendinimas:

                      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 && dėklas[stackIndex] != '(') { rezultatas[rezultatoIndeksas++] = dėklas[stackIndex--];  } stackIndex--; // Pop '(' } // Jei operatorius nuskaitomas 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) { rezultatas[rezultatoIndeksas++] = dėklas[stackIndex--];  } rezultatas[rezultato indeksas] = ' ';  printf('%s
', rezultatas); } // Tvarkyklės kodas int main() { char exp[] = 'a+b*(c^d-e)^(f+g*h)-i';  // Funkcijos iškvietimas infixToPostfix(exp);  grąžinti 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 = naujas Stack();  už (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)  {  Stackstack = naujas Stack();  Sąrašasrezultatas = naujas sąrašas();  už (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 '(' } // Jei operatorius nuskaitomas 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) { rezultatas.Pridėti(stack.Pop());  } Console.WriteLine(string.Join('', rezultatas));  } // Tvarkyklės kodas static void Main() { string exp = 'a+b*(c^d-e)^(f+g*h)-i';  // Funkcijos iškvietimas 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) {  stackst;  stygos rezultatas;  už (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; }>
                      Išvestis 
                      abcd^e-fgh*+^*+i->

                      Laiko sudėtingumas: O(N), kur N yra infikso išraiškos dydis
                      Pagalbinė erdvė: O(N), kur N yra infikso išraiškos dydis