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

*p1p2 return 1*/

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.