Conversão de infixo para pós-fixo. As pilhas são
usadas pelos compiladores para ajudar no processo de
avaliação de expressões e na geração de código em linguagem
de máquina. Neste e no próximo exercício, investigaremos
como os compiladores avaliam as expressões
aritméticas que consistem apenas em constantes,
operadores e parênteses.
Os seres humanos geralmente escrevem expressões como
3 + 4 e 7 / 9, em que o operador (+ ou / aqui) é escrito
entre seus operandos — isso é chamado de notação infixa.
Os computadores ‘preferem’ a notação pós-fixa, na
qual o operador é escrito à direita de seus dois operandos.
As expressões infixas precedentes apareceriam em notação
pós-fixa como 3 4 + e 7 9 /, respectivamente.
Para calcular uma expressão infixa complexa, um compilador
teria de, primeiro, converter a expressão para a notação
pós-fixa e, então, analisar e calcular a versão pós-fixa
da expressão. Cada um desses algoritmos exige somente
uma única passagem pela expressão, da esquerda para a
direita. Cada algoritmo usa um objeto pilha para suportar
sua operação e, em cada passagem do algoritmo, a pilha é
usada com uma finalidade diferente.
Nesse exercício, você escreverá uma versão do algoritmo de
conversão de notação infixa para pós-fixa. No próximo exercício,
você escreverá uma versão do algoritmo de análise da
expressão pós-fixa.
Escreva um programa que converta uma expressão aritmética
infixa comum (suponha que uma expressão válida
seja fornecida como entrada) com inteiros de um único
dígito, tal como
(6 + 2) * 5 - 8 / 4
para uma expressão pós-fixa. A versão pós-fixa da expressão
infixa do exemplo anterior é
6 2 + 5 * 8 4 / -
O programa deverá ler a expressão para o array de caracteres
infix e usar versões modificadas das funções de pilha
implementadas neste capítulo para ajudar a criar a expressão
pós-fixa em um array de caracteres postfix. O algoritmo
para se criar uma expressão pós-fixa é o seguinte:
1) Insira um parêntese à esquerda ‘(‘ no topo da pilha.
2) Acrescente um parêntese à direita ‘)’ ao final
de infix.
Passo 1
Neste exercício, precisamos escrever um programa que receba uma expressão com notação infixa e a converta em notação pós-fixada. Para fazer isso, aplique o algoritmo fornecido. O programa a seguir converte a notação infixa em notação pósfixa
Passo 2
#include
#include
#include
#include
/*Define structure and synonime*/
typedef struct stackNode{
char data;
struct stackNode *next;
} StackNode;
/*Define synonime for the pointer to stack*/
typedef StackNode *stack;
/*Prototypes*/
void convertToPostfix(char infix[], char postfix[]);
int isOperator(char c);
int precedence(char op1, char op2);
char stackTop(stack Stack);
void printStack(stack Stack);
void push(stack *Stack,char value);
char pop(stack *Stack);
int isEmpty(stack Stack);
int main(void){
char infix[100];
char postfix[100]="";
printf("Enter the expression: ");
scanf("%s",infix);
convertToPostfix(infix,postfix);
printf("%s",postfix);
return 0;
}
void convertToPostfix(char infix[], char postfix[]){
int idxIn=0, idxPost=0;
char popped;
char right = ')';
stack pStack = NULL;
/*Push left parenthesis onto stack*/
push(&pStack,'(');
/*Append right parenthesis to infix*/
strncat(infix,&right,1);
/*While stack is not empty*/
while(!isEmpty(pStack)){
/*If char is digit, copy to postfix*/
if(infix[idxIn]>=48 && infix[idxIn]
postfix[idxPost] = infix[idxIn];
idxPost++;
idxIn++;
}else if(infix[idxIn] == '('){
/*If char is (, push to stack*/
push(&pStack,infix[idxIn]);
idxIn++;
}else if(isOperator(infix[idxIn])){
/*If operator*/
while(isOperator(stackTop(pStack)) &&
precedence(stackTop(pStack),
infix[idxIn])>-1){
popped = pop(&pStack);
postfix[idxPost] = popped;
idxPost++;
}
push(&pStack,infix[idxIn]);
idxIn++;
}else if(infix[idxIn] == ')'){
/*Pop from stack, until (*/
popped = pop(&pStack);
while(popped != '('){
postfix[idxPost] = popped;
idxPost++;
popped = pop(&pStack);
}
idxIn++;
}
}
}
int isOperator(char c){
/*Check if char is operator*/
char operators[6]={'+','-','*','/','^','%'};
for(int i = 0; i
if(c == operators[i]){
return 1;
}
}
return 0;
}
Passo 3
int precedence(char op1, char op2){
/*Check the operator precedence
*Lowest precedence is 1, midlle 2, highest 3
*If operators have same precedence return 0, if
*p1
int p1,p2;
switch(op1){
case '+':
p1 = 1;
break;
case '-':
p1 = 1;
break;
case '*':
p1 = 2;
break;
case '/':
p1 = 2;
break;
case '%':
p1 = 2;
break;
case '^':
p1 = 3;
break;
}
switch(op2){
case '+':
p2 = 1;
break;
case '-':
p2 = 1;
break;
case '*':
p2 = 2;
break;
case '/':
p2 = 2;
break;
case '%':
p2 = 2;
break;
case '^':
p2 = 3;
break;
}
if(p1
return -1;
}else if(p1 > p2){
return 1;
}else{
return 0;
}
}
char stackTop(stack Stack){
char value;
if(Stack == NULL){
printf("The stack is empty");
}else{
value = Stack->data;
}
return value;
}
void printStack(stack Stack){
if(Stack == NULL){
printf("The stack is empty.");
}else{
while(Stack!=NULL){
printf("%c ", Stack->data);
Stack=Stack->next;
}
}
printf("\n");
}
void push(stack *Stack,char value){
StackNode *newNode;
newNode = malloc(sizeof(StackNode));
if(newNode == NULL){
printf("%s not added. Not enough memory");
}else{
/*Add value to node*/
newNode->data = value;
/*Set node to point at the top of the stack*/
newNode->next = *Stack;
/*New top of the stack*/
*Stack = newNode;
}
}
int isEmpty(stack Stack){
return Stack==NULL;
}
char pop(stack *current){
/*Temporary node pointer*/
stack temp;
char value;
if(isEmpty(*current)){
printf("The stack is empty");
}else{
temp = *current;
value = (*current)->data;
*current = (*current)->next;
free(temp);
}
return value;
}
A saída do programa dado é
Digite a expressão: (6+2)*5-8/4)
62+5*84/-
Resposta
Ver o desenvolvimento.