Infija a Postfix conversión que utilizan la pila [con el programa C]

aprender: Cómo convertir infijo a postfix que utilizan la pila en el programa de lenguaje C ? Infija a la conversión Postfix es una de las aplicaciones más importantes de la pila.

Una de las aplicaciones de la pila no quede en la conversión de expresiones aritméticas en lenguajes de programación de alto nivel en forma legible por máquina. A medida que nuestro sistema informático sólo puede entender y trabajar en un lenguaje binario, se supone que una operación aritmética puede tener lugar en sólo dos operandos por ejemplo, A + B, C * D, D / A etc, pero en nuestra forma habitual de una expresión aritmética puede consistir en más de un operador y por ejemplo dos operandos (A + B) * C (D / (J + D)) .

Estas operaciones aritméticas complejas se pueden convertir en notación polaca usando pilas que luego puede ser ejecutado en dos operandos y una forma de operador.

Infijo Expresión

Se sigue el esquema de & lt; operando & gt; & lt; operador & gt; & lt; operando & gt; es decir, una & lt; operador & gt; está precedido y sucedido por un & lt; operando & gt ;. Tal expresión se denomina expresión infija. Por ejemplo, A + B

Postfix Expresión

Se sigue el esquema de & lt; operando & gt; & lt; operando & gt; & lt; operador & gt; es decir, una & lt; operador & gt; se logrado tanto por el & lt; operando & gt ;. Por ejemplo, AB +

Algoritmo para convertir Infijo Para Postfix

Let, X es una expresión aritmética escrita en notación infija. Este algoritmo encuentra la expresión postfix equivalente Y .

  1. Push “(“en Stack, y añadir ‘)’ para el final de X.
  2. Scan X de izquierda a derecha y repita el paso 3 a 6 para cada elemento de X hasta que la pila está vacía.
  3. If un operando se encuentra, agregarlo a Y.
  4. If se encuentra un paréntesis izquierdo, empujarlo hacia la pila.
  5. If un operador se encuentra, entonces:

    1. repetidamente pop de Stack y añadir a cada operador Y (en la parte superior de la pila) que tiene la misma precedencia que o mayor precedencia de operador.
    2. Agregar operador Pila.
      [Fin del If]

  6. If se encuentra un paréntesis derecho, entonces:

    1. repetidamente pop de la pila y añadir a Y cada operador (en la parte superior de la pila) hasta que un paréntesis izquierdo se encuentra .
    2. Retire el paréntesis izquierdo.
      [Fin del If]
      [Fin del If]

  7. FIN.

Tomemos un ejemplo para entender mejor el algoritmo

Infijo Expresión: A + (B * C- (D / E ^ F) * G) * H , donde ^ es un operador exponencial.

resultante Postfix Expresión: ABC * DEF ^ / G * -H * +

Advantage de Postfix expresión sobre Infijo Expresión

Una expresión infija es difícil para la máquina para conocer y mantener un registro de precedencia de los operadores. Por otra parte, una expresión postfix en sí determina la precedencia de los operadores (como la colocación de los operadores en una expresión postfix depende de su prioridad) .Por lo tanto, para la máquina es más fácil de llevar a cabo una expresión de sufijo que una expresión infija.

C programa para convertir Infijo a Postfix Expresión


#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>
#define SIZE 100

char stack[SIZE];
int top = -1;

void push(char item)
{
if(top >= SIZE-1)
{
printf("nStack Overflow.");
}
else
{
top = top+1;
stack[top] = item;
}
}

char pop()
{
char item ;
if(top <0)
{
printf("stack under flow: invalid infix expression");
getchar();


exit(1);
}
else
{
item = stack[top];
top = top-1;
return(item);
}
}

int is_operator(char symbol)
{
if(symbol == '^' || symbol == '*' || symbol == '/' || symbol == '+' || symbol =='-')
{
return 1;
}
else
{
return 0;
}
}

int precedence(char symbol)
{
if(symbol == '^')
{
return(3);
}
else if(symbol == '*' || symbol == '/')
{
return(2);
}
else if(symbol == '+' || symbol == '-')
{
return(1);
}
else
{
return(0);
}
}
void InfixToPostfix(char infix_exp[], char postfix_exp[])
{
int i, j;
char item;
char x;
push('(');
strcat(infix_exp,")");
i=0;
j=0;
item=infix_exp[i];
while(item != '_CP0_')
{
if(item == '(')
{
push(item);
}
else if( isdigit(item) || isalpha(item))
{
postfix_exp[j] = item;
j++;
}
else if(is_operator(item) == 1)
{
x=pop();
while(is_operator(x) == 1 && precedence(x)>= precedence(item))
{
postfix_exp[j] = x;
j++;
x = pop();
}
push(x);

push(item);
}
else if(item == ')')
{
x = pop();
while(x != '(')
{
postfix_exp[j] = x;
j++;
x = pop();
}
}
else
{
printf("nInvalid infix Expression.n");
getchar();
exit(1);
}
i++;
item = infix_exp[i];
}
if(top>0)
{
printf("nInvalid infix Expression.n");
getchar();
exit(1);
}
if(top>0)
{
printf("nInvalid infix Expression.n");
getchar();
exit(1);
}
postfix_exp[j] = '_CP0_';

}

int main()
{
char infix[SIZE], postfix[SIZE];

printf("ASSUMPTION: The infix expression contains single letter variables and single digit constants only.n");
printf("nEnter Infix expression : ");
gets(infix);
InfixToPostfix(infix,postfix);
printf("Postfix Expression: ");
puts(postfix);
return 0;
}

salida

First Run:
Enter Infix expression : A+(B*C-(D/E^F)*G)*H
Postfix Expression: ABC*DEF^/G*-H*+
Second Run:
Enter Infix expression : (3^2*5)/(3*2-3)+5
Postfix Expression: 32^5*32*3-/5+


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *