Napisz program konwertujący wyrażenie Infix na postać Postfix.

Wyrażenie wrostkowe: Wyrażenie postaci operatora b (a + b), tj. gdy operator znajduje się pomiędzy każdą parą operandów.
Wyrażenie postfiksowe: Wyrażenie postaci a operator b (ab+), tj. gdy po każdej parze operandów następuje operator.

Przykłady:

Wejście: A + B * C + D
Wyjście: ABC**+D+

Wejście: ((A + B) – C * (D / E)) + F
Wyjście: AB+CDE/*-F+

Dlaczego postfiksowa reprezentacja wyrażenia?

Kompilator skanuje wyrażenie od lewej do prawej lub od prawej do lewej.
Rozważ wyrażenie: a + b * c + d

• Kompilator najpierw skanuje wyrażenie, aby ocenić wyrażenie b * c, a następnie ponownie skanuje wyrażenie, aby dodać do niego a.
• Wynik jest następnie dodawany do d po kolejnym skanowaniu.

Powtarzające się skanowanie sprawia, że ​​jest ono bardzo nieefektywne. Wyrażenia infiksowe są łatwo czytelne i możliwe do rozwiązania przez ludzi, podczas gdy komputer nie może łatwo rozróżnić operatorów i nawiasów, dlatego przed oceną lepiej jest przekonwertować wyrażenie na formę postfiksu (lub przedrostka).

Odpowiednie wyrażenie w formie przyrostkowej to abc*+d+ . Wyrażenia przyrostkowe można łatwo ocenić za pomocą stosu.

Jak przekonwertować wyrażenie Infix na wyrażenie Postfix?

Aby przekonwertować wyrażenie infix na wyrażenie postfix, użyj metody Poniżej znajdują się kroki umożliwiające wdrożenie powyższego pomysłu:

1. Zeskanuj wyrażenie wrostkowe od lewej do prawej .

2. Poniżej znajdują się kroki umożliwiające wdrożenie powyższego pomysłu:
   1. Jeśli skanowany znak jest operandem, umieść go w wyrażeniu przyrostkowym.
   3. Poniżej znajdują się kroki umożliwiające wdrożenie powyższego pomysłu:
      1. W przeciwnym razie wykonaj następujące czynności
         • Jeżeli pierwszeństwo i powiązanie zeskanowanego operatora są większe niż pierwszeństwo i powiązanie operatora na stosie [lub stos jest pusty lub stos zawiera znak „ ( „ ], a następnie włóż go na stos. [’ ^ operator „jest prawoskojarzeniowy, a inne operatory, takie jak” + ',' – ',' * ' I ' / „są lewicowo-stowarzyszeniowe].
           • Sprawdź zwłaszcza stan, w którym operator na górze stosu i operator zeskanowany są „ ^ „. W tym stanie pierwszeństwo skanowanego operatora jest wyższe ze względu na jego prawą asocjatywność. Zostanie więc wepchnięty na stos operatorów.
           • We wszystkich pozostałych przypadkach, gdy szczyt stosu operatorów jest taki sam jak operator skanowany, usuń operator ze stosu ze względu na lewą asocjatywność, przez co operator zeskanowany ma mniejszy priorytet.
         • W przeciwnym razie usuń ze stosu wszystkie operatory, które mają pierwszeństwo większe lub równe niż operator zeskanowany.
           • Po wykonaniu tej czynności Wciśnij zeskanowanego operatora na stos. (Jeśli podczas otwierania napotkasz nawias, zatrzymaj się w tym miejscu i włóż zeskanowany operator na stos.)
      4. Poniżej znajdują się kroki umożliwiające wdrożenie powyższego pomysłu:
         1. Jeśli zeskanowany znak to „ ( ', włóż go na stos.
         5. Poniżej znajdują się kroki umożliwiające wdrożenie powyższego pomysłu:
            1. Jeśli zeskanowany znak to „ ) ”, zdejmij stos i wyprowadź go, aż pojawi się „ ( ' zostanie napotkany i odrzuć oba nawiasy.
            6. Poniżej znajdują się kroki umożliwiające wdrożenie powyższego pomysłu:
               1. Powtórz kroki 2-5 do momentu przeskanowania wyrażenia infiksowego.
               7. Poniżej znajdują się kroki umożliwiające wdrożenie powyższego pomysłu:

                  wiersz kontra kolumna

                  1. Po zakończeniu skanowania otwórz stos i dodaj operatory w wyrażeniu przyrostkowym, aż nie będzie pusty.
                  8. Poniżej znajdują się kroki umożliwiające wdrożenie powyższego pomysłu:
                     1. Na koniec wydrukuj wyrażenie przyrostkowe.

                     Poniżej znajdują się kroki umożliwiające wdrożenie powyższego pomysłu:

                     1. Ilustracja:

                     Poniżej znajdują się kroki umożliwiające wdrożenie powyższego pomysłu:

                     1. Aby lepiej zrozumieć, postępuj zgodnie z poniższą ilustracją
                        Poniżej znajdują się kroki umożliwiające wdrożenie powyższego pomysłu:

                        1. Rozważmy wyrażenie wrostkowe exp = a+b*c+d
                           a wyrażenie infiksowe jest skanowane za pomocą iteratora I , który jest inicjowany jako ja = 0 .

                           Pierwszy krok: Tutaj i = 0 i exp[i] = „a”, tj. operand. Dodaj to więc do wyrażenia postfiksowego. Dlatego, postfix = a .

                           

                           Dodaj „a” w postfiksie

                           Drugi krok: Tutaj i = 1 i exp[i] = „+”, czyli operator. Włóż to do stosu. postfix = a I stos = {+} .

                           

                           Wciśnij „+” na stosie

                           Trzeci krok: Teraz i = 2 i exp[i] = „b”, tj. operand. Dodaj to więc do wyrażenia postfiksowego. postfix = ab I stos = {+} .

                           

                           Dodaj „b” w postfiksie

                           4. krok: Teraz i = 3 i exp[i] = „*”, czyli operator. Włóż to do stosu. postfix = ab I stos = {+, *} .

                           

                           Wciśnij „*” na stosie

                           5. krok: Teraz i = 4 i exp[i] = „c”, tj. operand. Dodaj to w wyrażeniu przyrostkowym. postfiks = abc I stos = {+, *} .

                           

                           Dodaj „c” w postfiksie

                           6. krok: Teraz i = 5 i exp[i] = „+”, czyli operator. Najwyższy element stosu ma wyższy priorytet. Więc pop, aż stos stanie się pusty lub górny element będzie miał mniejszy priorytet. „*” jest wyskakujący i dodawany w postfiksie. Więc postfiks = abc* I stos = {+} .

                           

                           Naciśnij „*” i dodaj postfiks

                           Teraz górnym elementem jest „ + „to również nie ma mniejszego priorytetu. Otwórz. postfiks = abc**+ .

                           

                           Naciśnij „+” i dodaj go w postfixie

                           Teraz stos jest pusty. Więc pchnij „+” w stosie. stos = {+} .

                           

                           Wciśnij „+” na stosie

                           7. krok: Teraz i = 6 i exp[i] = „d”, tj. operand. Dodaj to w wyrażeniu przyrostkowym. postfiks = abc*+d .

                           

                           Dodaj „d” w postfiksie

                           Ostatni krok: Teraz nie ma już żadnego elementu. Opróżnij więc stos i dodaj go w wyrażeniu postfiksowym. postfiks = abc*+d+ .

                           

                           Naciśnij „+” i dodaj go w postfixie

                           Poniżej implementacja powyższego algorytmu:

                           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 && stos[indeksstosu] != '(') { wynik[wynikIndeks++] = stos[Indeksstosu--];  } indeks stosu--; // Pop '(' } // Jeśli operator jest skanowany 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) { wynik[resultIndex++] = stos[stackIndex--];  } wynik[resultIndex] = ' ';  printf('%s
                           ', wynik); } // Kod sterownika int main() { char exp[] = 'a+b*(c^d-e)^(f+g*h)-i';  // Wywołanie funkcji infixToPostfix(exp);  zwróć 0; }>

                           Jawa

                           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();  Stackstos = nowy stos();  for (int i = 0; tj< 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);  } }>

                           Pyton

                           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)  {  Stackstos = nowy stos();  Listawynik = nowa lista();  for (int i = 0; tj< 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() != '(') { wynik.Add(stack.Pop());  } stos.Pop(); // Pop '(' } // Jeśli operator jest skanowany 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) { wynik.Dodaj(stack.Pop());  } Console.WriteLine(string.Join('', wynik));  } // Kod sterownika static void Main() { string exp = 'a+b*(c^d-e)^(f+g*h)-i';  // Wywołanie funkcji 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.;  wynik ciągu;  for (int i = 0; tj< 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; }>

                           
                           Wyjście

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

                           Złożoność czasowa: O(N), gdzie N jest rozmiarem wyrażenia wrostkowego
                           Przestrzeń pomocnicza: O(N), gdzie N jest rozmiarem wyrażenia wrostkowego