Напишіть програму для перетворення виразу Infix у форму Postfix.

Інфіксний вираз: Вираз у формі оператора b (a + b), тобто коли оператор знаходиться між кожною парою операндів.
Постфіксний вираз: Вираз у формі оператора a b (ab+), тобто коли за кожною парою операндів слідує оператор.

приклади:

введення: A + B * C + D
Вихід: ABC*+D+

введення: ((A + B) – C * (D / E)) + F
Вихід: AB+CDE/*-F+

Чому постфіксне представлення виразу?

Компілятор сканує вираз або зліва направо, або справа наліво.
Розглянемо вираз: a + b * c + d

• Компілятор спочатку сканує вираз, щоб обчислити вираз b * c, потім знову сканує вираз, щоб додати до нього a.
• Потім результат додається до d після ще одного сканування.

Багаторазове сканування робить його дуже неефективним. Інфіксні вирази легко читаються та розв’язуються людьми, тоді як комп’ютер не може легко розрізнити оператори та круглі дужки, тому перед оцінкою краще перетворити вираз у постфіксну (або префіксну) форму.

Відповідний вираз у постфіксній формі є abc*+d+ . Постфіксні вирази можна легко обчислити за допомогою стека.

Як перетворити вираз Infix на вираз Postfix?

Щоб перетворити інфіксний вираз на постфіксний вираз, використовуйте Нижче наведено кроки для реалізації вищезазначеної ідеї:

1. Відскануйте інфіксний вираз зліва направо .

2. Нижче наведено кроки для реалізації вищезазначеної ідеї:
   1. Якщо сканований символ є операндом, помістіть його в постфіксний вираз.
   3. Нижче наведено кроки для реалізації вищезазначеної ідеї:
      1. В іншому випадку виконайте наступне
         • Якщо пріоритет і асоціативність сканованого оператора більші за пріоритет і асоціативність оператора в стеку [або стек порожній, або стек містить ‘ ( ‘ ], потім помістіть його в стек. [' ^ «оператор правильно асоціативний та інші оператори, такі як « + ',' – ',' * 'і' / ‘ є лівоасоціативними].
           • Особливо перевірте умову, коли оператор у верхній частині стека та сканований оператор є « ^ ‘. У цій умові пріоритет сканованого оператора вищий через його праву асоціативність. Тож його буде вставлено в стек оператора.
           • У всіх інших випадках, коли вершина стека операторів збігається зі сканованим оператором, тоді оператор витягується зі стеку через ліву асоціативність, через яку сканований оператор має менший пріоритет.
         • Інакше вилучити зі стеку всі оператори, пріоритет яких перевищує або дорівнює пріоритету сканованого оператора.
           • Після цього помістіть відсканованого оператора в стек. (Якщо ви зіткнетеся з круглими дужками під час відкриття, зупиніться на цьому та помістіть сканований оператор у стек.)
      4. Нижче наведено кроки для реалізації вищезазначеної ідеї:
         1. Якщо сканований символ є « ( «, посуньте його до стека.
         5. Нижче наведено кроки для реалізації вищезазначеної ідеї:
            1. Якщо сканований символ є « ) ', витягніть стек і виведіть його, доки не з'явиться ' ( «, і відкиньте обидві дужки.
            6. Нижче наведено кроки для реалізації вищезазначеної ідеї:
               1. Повторіть кроки 2-5 доки інфіксний вираз не буде відскановано.
               7. Нижче наведено кроки для реалізації вищезазначеної ідеї:

                  бази даних

                  1. Після завершення сканування витягніть стек і додайте оператори в постфіксний вираз, доки він не стане порожнім.
                  8. Нижче наведено кроки для реалізації вищезазначеної ідеї:
                     1. Нарешті, виведіть постфіксний вираз.

                     Нижче наведено кроки для реалізації вищезазначеної ідеї:

                     1. Ілюстрація:

                     Нижче наведено кроки для реалізації вищезазначеної ідеї:

                     1. Дотримуйтесь ілюстрації нижче для кращого розуміння
                        Нижче наведено кроки для реалізації вищезазначеної ідеї:

                        1. Розглянемо інфіксний вираз exp = a+b*c+d
                           а інфіксний вираз сканується за допомогою ітератора i , який ініціалізується як i = 0 .

                           1-й крок: Тут i = 0 і exp[i] = ‘a’, тобто операнд. Тож додайте це в постфіксний вираз. тому постфікс = а .

                           

                           Додайте «а» в постфікс

                           2-й крок: Тут i = 1 і exp[i] = ‘+’, тобто оператор. Вставте це в стек. постфікс = а і стек = {+} .

                           

                           Натисніть «+» у стеку

                           3-й крок: Тепер i = 2 і exp[i] = ‘b’, тобто операнд. Тож додайте це в постфіксний вираз. постфікс = ab і стек = {+} .

                           

                           Додайте «b» у постфіксі

                           4-й крок: Тепер i = 3 і exp[i] = ‘*’, тобто оператор. Вставте це в стек. постфікс = ab і стек = {+, *} .

                           

                           Натисніть «*» у стек

                           5-й крок: Тепер i = 4 і exp[i] = ‘c’, тобто операнд. Додайте це в постфіксний вираз. постфікс = abc і стек = {+, *} .

                           

                           Додайте «с» у постфіксі

                           6-й крок: Тепер i = 5 і exp[i] = ‘+’, тобто оператор. Найвищий елемент стека має вищий пріоритет. Тож витягуйте, доки стек не стане порожнім або верхній елемент матиме менший пріоритет. «*» висувається та додається в постфікс. Так постфікс = abc* і стек = {+} .

                           

                           Підніміть «*» і додайте постфікс

                           Тепер верхній елемент ' + «це також має не менший пріоритет. Лопни це. постфікс = abc*+ .

                           

                           Підніміть «+» і додайте його в постфікс

                           Тепер стек порожній. Так штовхайся '+' в стеку. стек = {+} .

                           

                           Натисніть «+» у стеку

                           7-й крок: Тепер i = 6 і exp[i] = ‘d’, тобто операнд. Додайте це в постфіксний вираз. постфікс = abc*+d .

                           

                           Додайте «d» у постфіксі

                           Останній крок: Тепер не залишилося жодного елемента. Отже, очистіть стек і додайте його в постфіксний вираз. постфікс = abc*+d+ .

                           

                           Підніміть «+» і додайте його в постфікс

                           Нижче наведено реалізацію наведеного вище алгоритму:

                           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 '(' } // Якщо оператор сканується 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) {результат[resultIndex++] = stack[stackIndex--];  } результат[індекс результату] = ' ';  printf('%s
                           ', результат); } // Код драйвера int main() { char exp[] = 'a+b*(c^d-e)^(f+g*h)-i';  // Виклик функції infixToPostfix(exp);  повернути 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();  Stackстек = новий стек();  для (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)  {  Stackстек = новий стек();  Списокрезультат = новий список();  для (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 '(' } // Якщо оператор сканується 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) { result.Add(stack.Pop());  } Console.WriteLine(string.Join('', результат));  } // Код драйвера static void Main() { string exp = 'a+b*(c^d-e)^(f+g*h)-i';  // Виклик функції 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;  результат рядка;  для (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; }>

                           
                           Вихід

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

                           Часова складність: O(N), де N - розмір інфіксного виразу
                           Допоміжний простір: O(N), де N - розмір інфіксного виразу