Scrivere un programma per convertire un'espressione infissa nella forma suffissa.

Espressione infissa: L'espressione della forma a dell'operatore b (a + b), ovvero quando un operatore si trova tra ogni coppia di operandi.
Espressione suffissa: L'espressione dell'operatore della forma a b (ab+), ovvero quando ogni coppia di operandi è seguita da un operatore.

Esempi:

Ingresso: A+B*C+D
Produzione: ABC*+D+

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

Perché la rappresentazione suffissa dell'espressione?

Il compilatore esegue la scansione dell'espressione da sinistra a destra o da destra a sinistra.
Consideriamo l'espressione: a+b*c+d

• Il compilatore innanzitutto esegue la scansione dell'espressione per valutare l'espressione b * c, quindi esegue nuovamente la scansione dell'espressione per aggiungervi a.
• Il risultato viene quindi aggiunto a d dopo un'altra scansione.

La scansione ripetuta lo rende molto inefficiente. Le espressioni infisse sono facilmente leggibili e risolvibili dagli esseri umani mentre il computer non può distinguere facilmente gli operatori e le parentesi, quindi è meglio convertire l'espressione nella forma suffissa (o prefissa) prima della valutazione.

L'espressione corrispondente in forma suffissa è abc*+d+ . Le espressioni suffisse possono essere valutate facilmente utilizzando uno stack.

Come convertire un'espressione infissa in un'espressione suffissa?

Per convertire un'espressione infissa in un'espressione suffissa, utilizzare il comando Di seguito sono riportati i passaggi per implementare l'idea di cui sopra:

1. Scansiona l'espressione infissa da sinistra a destra .

2. Di seguito sono riportati i passaggi per implementare l'idea di cui sopra:
   1. Se il carattere scansionato è un operando, inserirlo nell'espressione suffissa.
   3. Di seguito sono riportati i passaggi per implementare l'idea di cui sopra:
      1. Altrimenti, procedi come segue
         • Se la precedenza e l'associatività dell'operatore scansionato sono maggiori della precedenza e dell'associatività dell'operatore nello stack [o lo stack è vuoto o lo stack contiene un ' ( ‘], quindi mettilo nello stack. [' ^ ‘ l’operatore è associativo giusto e altri operatori come ‘ + ',' – ',' * ' E ' / ‘ sono associativi a sinistra].
           • Controllare soprattutto la condizione in cui l'operatore in cima alla pila e l'operatore scansionato sono entrambi ' ^ ‘. In questa condizione la precedenza dell'operatore scansionato è maggiore a causa della sua giusta associatività. Quindi verrà inserito nello stack dell'operatore.
           • In tutti gli altri casi, quando la parte superiore dello stack degli operatori è uguale all'operatore scansionato, estrarre l'operatore dallo stack a causa dell'associatività sinistra grazie alla quale l'operatore scansionato ha meno precedenza.
         • Altrimenti, estrai dallo stack tutti gli operatori che hanno la precedenza o sono uguali a quelli dell'operatore scansionato.
           • Dopo averlo fatto, spingi l'operatore scansionato nella pila. (Se incontri delle parentesi mentre fai scoppiare, fermati lì e spingi l'operatore scansionato nello stack.)
      4. Di seguito sono riportati i passaggi per implementare l'idea di cui sopra:
         1. Se il carattere scansionato è un ' ( ', mettilo in pila.
         5. Di seguito sono riportati i passaggi per implementare l'idea di cui sopra:
            1. Se il carattere scansionato è un ' ) ', apri lo stack e generalo fino a quando non appare un ' ( ' si incontra e scartare entrambe le parentesi.
            6. Di seguito sono riportati i passaggi per implementare l'idea di cui sopra:
               1. Ripeti i passaggi 2-5 finché l'espressione infissa non viene scansionata.
               7. Di seguito sono riportati i passaggi per implementare l'idea di cui sopra:

                  cento contro rhel

                  1. Una volta terminata la scansione, pop lo stack e aggiungi gli operatori nell'espressione suffissa finché non è vuota.
                  8. Di seguito sono riportati i passaggi per implementare l'idea di cui sopra:
                     1. Infine, stampa l'espressione suffissa.

                     Di seguito sono riportati i passaggi per implementare l'idea di cui sopra:

                     1. Illustrazione:

                     Di seguito sono riportati i passaggi per implementare l'idea di cui sopra:

                     1. Seguire l'illustrazione seguente per una migliore comprensione
                        Di seguito sono riportati i passaggi per implementare l'idea di cui sopra:

                        1. Consideriamo l'espressione infissa esp = a+b*c+d
                           e l'espressione infissa viene scansionata utilizzando l'iteratore io , che viene inizializzato come io = 0 .

                           1° passo: Qui i = 0 ed exp[i] = 'a' cioè un operando. Quindi aggiungilo nell'espressione suffissa. Perciò, suffisso = a .

                           

                           Aggiungi 'a' nel suffisso

                           2° passo: Qui i = 1 ed exp[i] = '+' cioè un operatore. Mettilo nello stack. suffisso = a E pila = {+} .

                           

                           Premi '+' nello stack

                           3° passo: Ora i = 2 ed exp[i] = 'b' cioè un operando. Quindi aggiungilo nell'espressione suffissa. suffisso = ab E pila = {+} .

                           

                           Aggiungi 'b' nel suffisso

                           4° passo: Ora i = 3 ed exp[i] = ‘*’ cioè un operatore. Mettilo nello stack. suffisso = ab E pila = {+, *} .

                           

                           Premi '*' nello stack

                           5° passo: Ora i = 4 ed exp[i] = 'c' cioè un operando. Aggiungilo nell'espressione suffissa. suffisso = abc E pila = {+, *} .

                           

                           Aggiungi 'c' nel suffisso

                           6° passo: Ora i = 5 ed exp[i] = '+' cioè un operatore. L'elemento più in alto dello stack ha la precedenza più alta. Quindi fai scoppiare finché lo stack non diventa vuoto o l'elemento in alto ha meno precedenza. '*' viene estratto e aggiunto in suffisso. COSÌ suffisso = abc* E pila = {+} .

                           

                           Seleziona '*' e aggiungi il suffisso

                           Ora l'elemento superiore è ' + ‘anche questo non ha meno precedenza. Pop. suffisso = abc*+ .

                           

                           Fai clic su '+' e aggiungilo in suffisso

                           Ora lo stack è vuoto. Quindi spingi '+' nella pila. pila = {+} .

                           

                           Premi '+' nello stack

                           7° passo: Ora i = 6 ed exp[i] = 'd' cioè un operando. Aggiungilo nell'espressione suffissa. suffisso = abc*+d .

                           

                           Aggiungi 'd' nel suffisso

                           Passo finale: Ora non è rimasto alcun elemento. Quindi svuota lo stack e aggiungilo nell'espressione suffissa. suffisso = abc*+d+ .

                           

                           Fai clic su '+' e aggiungilo in suffisso

                           Di seguito è riportata l'implementazione dell'algoritmo di cui sopra:

                           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] != '(') { risultato[resultIndex++] = stack[stackIndex--];  } stackIndex--; // Pop '(' } // Se viene scansionato un operatore 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) { risultato[risultatoIndex++] = stack[stackIndex--];  } risultato[indicerisultato] = ' ';  printf('%s
                           ', risultato); } // Codice driver int main() { char exp[] = 'a+b*(c^d-e)^(f+g*h)-i';  // Chiamata di funzione infixToPostfix(exp);  restituire 0; }>

                           Giava

                           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();  Stackpila = nuova pila();  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);  } }>

                           Pitone

                           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)  {  Stackpila = nuova pila();  Elencorisultato = nuova lista();  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 && stack.Peek() != '(') { risultato.Add(stack.Pop());  } stack.Pop(); // Pop '(' } // Se un operatore viene scansionato 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) { risultato.Add(stack.Pop());  } Console.WriteLine(string.Join('', risultato));  } // Codice driver static void Main() { string exp = 'a+b*(c^d-e)^(f+g*h)-i';  // Chiamata di funzione 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;  risultato della stringa;  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; }>

                           
                           Produzione

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

                           Complessità temporale: O(N), dove N è la dimensione dell'espressione infissa
                           Spazio ausiliario: O(N), dove N è la dimensione dell'espressione infissa