logo

TechCodeview

Previesť výraz Infix na výraz Postfix

Napíšte program na konverziu výrazu Infix na formu Postfixu.

Infixný výraz: Vyjadrenie vo forme operátora b (a + b), t.j. keď je operátor medzi každým párom operandov.
Postfixový výraz: Výraz operátora vo forme ab (ab+), t.j. keď za každým párom operandov nasleduje operátor.



Príklady:

Vstup: A + B * C + D
Výkon: ABC*+D+

Vstup: ((A + B) – C * (D / E)) + F
Výkon: AB+CDE/*-F+



Prečo postfixová reprezentácia výrazu?

Kompilátor skenuje výraz buď zľava doprava, alebo sprava doľava.
Zvážte výraz: a + b * c + d

  • Kompilátor najprv skenuje výraz, aby vyhodnotil výraz b * c, potom znova skenuje výraz, aby k nemu pridal a.
  • Výsledok sa potom pripočíta k d po ďalšom skenovaní.

Opakované skenovanie ho robí veľmi neefektívnym. Infixové výrazy sú ľahko čitateľné a riešiteľné pre ľudí, zatiaľ čo počítač nedokáže ľahko rozlíšiť operátory a zátvorky, preto je lepšie výraz pred vyhodnotením previesť do postfixovej (alebo predponovej) formy.

Zodpovedajúci výraz vo forme postfixu je abc*+d+ . Postfixové výrazy možno ľahko vyhodnotiť pomocou zásobníka.



Ako previesť výraz Infix na výraz Postfix?

Ak chcete previesť výraz infix na výraz postfix, použite príkaz Nižšie sú uvedené kroky na implementáciu vyššie uvedenej myšlienky:

  1. Naskenujte infixový výraz zľava doprava .

  2. Nižšie sú uvedené kroky na implementáciu vyššie uvedenej myšlienky:

    1. Ak je naskenovaný znak operand, vložte ho do postfixového výrazu.
    2. Nižšie sú uvedené kroky na implementáciu vyššie uvedenej myšlienky:

      1. V opačnom prípade postupujte nasledovne
        • Ak je priorita a asociativita naskenovaného operátora väčšia ako priorita a asociativita operátora v zásobníku [alebo je zásobník prázdny alebo zásobník obsahuje „ ( ‘ ], potom ho zatlačte do stohu. [‘ ^ „operátor je správne asociatívny a iné operátory ako „ + ',' – ',' * „a“ / „sú ľavo-asociatívne].
          • Skontrolujte najmä stav, keď operátor na vrchu stohu a naskenovaný operátor sú „ ^ ‘. V tomto stave je prednosť skenovaného operátora vyššia vďaka jeho pravej asociativite. Takže bude zatlačený do zásobníka operátora.
          • Vo všetkých ostatných prípadoch, keď je horná časť zásobníka operátorov rovnaká ako naskenovaný operátor, potom operátor vytiahnite zo zásobníka z dôvodu ľavostrannej asociatívnosti, vďaka ktorej má naskenovaný operátor menšiu prednosť.
        • V opačnom prípade vyberte všetky operátory zo zásobníka, ktorých priorita je väčšia alebo rovnaká ako priorita naskenovaného operátora.
          • Potom zatlačte naskenovaný operátor do stohu. (Ak pri vyskakovaní narazíte na zátvorky, zastavte sa a zatlačte naskenovaný operátor do zásobníka.)
      2. Nižšie sú uvedené kroky na implementáciu vyššie uvedenej myšlienky:

        1. Ak je naskenovaný znak „ ( ‘, zatlačte ho do stohu.
        2. Nižšie sú uvedené kroky na implementáciu vyššie uvedenej myšlienky:

          1. Ak je naskenovaný znak „ ) “, vyklopte zásobník a vytlačte ho, kým sa „ ( ‘ sa stretnete a zahoďte obe zátvorky.
          2. Nižšie sú uvedené kroky na implementáciu vyššie uvedenej myšlienky:

            1. Opakujte kroky 2-5 kým sa nenaskenuje infixový výraz.
            2. Nižšie sú uvedené kroky na implementáciu vyššie uvedenej myšlienky:

              jtlačidlo
              1. Po dokončení skenovania vyklopte zásobník a pridajte operátory do výrazu postfix, kým nebude prázdny.
              2. Nižšie sú uvedené kroky na implementáciu vyššie uvedenej myšlienky:

                1. Nakoniec vytlačte postfixový výraz.

                  2. Nižšie sú uvedené kroky na implementáciu vyššie uvedenej myšlienky:

                  1. Ilustrácia:

                  Nižšie sú uvedené kroky na implementáciu vyššie uvedenej myšlienky:

                  1. Pre lepšie pochopenie postupujte podľa nižšie uvedeného obrázku

                    Nižšie sú uvedené kroky na implementáciu vyššie uvedenej myšlienky:

                    1. Zvážte infixový výraz exp = a+b*c+d
                      a infixový výraz sa naskenuje pomocou iterátora i , ktorý je inicializovaný ako i = 0 .

                      1. krok: Tu i = 0 a exp[i] = „a“, t.j. operand. Takže to pridajte do výrazu postfix. preto postfix = a .

                      Pridať

                      Pridajte „a“ do postfixu

                      2. krok: Tu i = 1 a exp[i] = „+“, t.j. operátor. Zatlačte to do stohu. postfix = a a zásobník = {+} .

                      TAM

                      Stlačte „+“ v zásobníku

                      3. krok: Teraz i = 2 a exp[i] = „b“, t. j. operand. Takže to pridajte do výrazu postfix. postfix = ab a zásobník = {+} .

                      gfg

                      Pridajte „b“ do postfixu

                      4. krok: Teraz i = 3 a exp[i] = „*“, t.j. operátor. Zatlačte to do stohu. postfix = ab a zásobník = {+, *} .

                      TAM

                      Stlačte „*“ v zásobníku

                      5. krok: Teraz i = 4 a exp[i] = „c“, t.j. operand. Pridajte to do výrazu postfix. postfix = abc a zásobník = {+, *} .

                      Pridať

                      Pridajte „c“ do postfixu

                      6. krok: Teraz i = 5 a exp[i] = „+“, t.j. operátor. Najvyšší prvok zásobníka má vyššiu prioritu. Takže pop, kým sa zásobník nevyprázdni alebo horný prvok nebude mať menšiu prednosť. „*“ sa objaví a pridá sa do postfixu. Takže postfix = abc* a zásobník = {+} .

                      Pop

                      Pop „*“ a pridajte postfix

                      Teraz je vrchný prvok „ + ‘ to tiež nemá menšiu prednosť. Praskni to. postfix = abc*+ .

                      Pop

                      Vyberte „+“ a pridajte ho do postfixu

                      Teraz je zásobník prázdny. Tak zatlačte '+' v zásobníku. zásobník = {+} .

                      TAM

                      Stlačte „+“ v zásobníku

                      7. krok: Teraz i = 6 a exp[i] = „d“, t. j. operand. Pridajte to do výrazu postfix. postfix = abc*+d .

                      Pridať

                      Pridajte „d“ do postfixu

                      Posledný krok: Teraz nezostal žiadny prvok. Takže vyprázdnite zásobník a pridajte ho do výrazu postfix. postfix = abc*+d+ .

                      Pop

                      Vyberte „+“ a pridajte ho do postfixu

                      Nižšie je uvedená implementácia vyššie uvedeného algoritmu:

                      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] != '(') { result[resultIndex++] = stack[stackIndex--];  } stackIndex--; // Pop '(' } // Ak je operátor skenovaný 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) { vysledok[resultIndex++] = stack[stackIndex--];  } vysledok[index vysledku] = ' ';  printf('%s
', vysledok); } // Kód ovládača int main() { char exp[] = 'a+b*(c^d-e)^(f+g*h)-i';  // Volanie funkcie infixToPostfix(exp);  návrat 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();  Stackzásobník = nový zásobník ();  pre (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)  {  Stackzásobník = nový zásobník();  Zoznamvýsledok = nový zoznam();  pre (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 '(' } // Ak je operátor skenovaný 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) { vysledok.Pridat(stack.Pop());  } Console.WriteLine(string.Join('', vysledok));  } // Kód ovládača static void Main() { string exp = 'a+b*(c^d-e)^(f+g*h)-i';  // Volanie funkcie 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;  výsledok reťazca;  pre (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; }>
                      Výkon 
                      abcd^e-fgh*+^*+i->

                      Časová zložitosť: O(N), kde N je veľkosť infixového výrazu
                      Pomocný priestor: O(N), kde N je veľkosť infixového výrazu