Avaliador de notação pós-fixada. Escreva um programa

que avalie uma expressão pós-fixa (suponha que

ela seja válida), tal como

6 2 + 5 * 8 4 / -

O programa deve ler uma expressão pós-fixa que consista

em dígitos isolados e operadores para um array de caracteres.

Usando versões modificadas das funções de pilha

implementadas anteriormente neste capítulo, o programa

deve percorrer a expressão e calculá-la. O algoritmo

é o seguinte:

1) Acrescente o caractere nulo (‘\0’) ao fim da expressão

pós-fixa. Quando o caractere nulo for encontrado,

nenhum processamento adicional será necessário.

2) Enquanto ‘\0’ não for encontrado, leia a expressão,

da esquerda para a direita.

Se o caractere atual for um dígito,

Insira seu valor inteiro no topo da pilha (o

valor inteiro de um caractere que é um dígito

é o seu valor no conjunto de caracteres do

computador menos o valor de ‘0’ no conjunto

de caracteres do computador).

Caso contrário, se o caractere atual for um

operador,

Remova os dois elementos do topo da pilha

para as variáveis x e y.

Calcule y operador x.

Insira o resultado do cálculo no topo da pilha.

3) Quando o caractere nulo for encontrado na expressão,

remova o valor do topo da pilha. Este é o resultado

da expressão pós-fixa.

[Nota: na etapa (2) anterior, se o operador for ‘/’, o

topo da pilha será 2, e o próximo elemento na pilha será

8, então remova 2 da pilha e o atribua a x, remova 8 para

y, calcule 8/2 e insira o resultado, 4, de volta no topo

da pilha. Essa nota também se aplica ao operador ‘-’.]

As operações aritméticas permitidas em uma expressão são:

+ adição

– subtração

* multiplicação

/ divisão

^ exponenciação

% módulo

A pilha deve ser mantida com as seguintes declarações:

struct stackNode {

int data;

struct stackNode *nextPtr;

};

typedef struct stackNode StackNode;

typedef StackNode *StackNodePtr;

O programa deve consistir em main e em outras seis funções

com os seguintes cabeçalhos:

int evaluatePostfixExpression( char

*expr )

Avalia a expressão pós-fixa.

int calculate( int op1, int op2, char

operator )

Avalia a expressão op1 operador op2.

void push( StackNodePtr *topPtr, int

value )

Insere um valor na pilha.

int pop( StackNodePtr *topPtr )

Retira um valor da pilha.

int isEmpty( StackNodePtr topPtr )

Determina se a pilha está vazia.

void printStack( StackNodePtr topPtr )

Imprime a pilha.

Passo 1

Neste exercício, precisamos escrever um programa que avalie uma expressão pós-fixada. O programa toma a expressão postfix como uma string de caracteres, adiciona o caractere nulo ao final da string e usa a pilha para avaliar a expressão. O programa pega char por char da expressão. Se o caractere for um dígito, o programa a empurra para a pilha. Se o caractere for operador, o programa pega os dígitos da pilha e calcula o valor da expressão usando os dois dígitos da pilha e o operador fornecido. O resultado é enviado para a pilha. Este processo se repete até que o final da string seja alcançado. Quando o final da string é alcançado, o programa retira o valor da pilha. Este valor é o resultado final.

Passo 2

O programa a seguir usa uma pilha para avaliar a expressão pós-fixada.

#include

#include

#include

#include

/*Definir estrutura e sinônimo*/

typedef struct stackNode{

char data;

struct stackNode *next;

} StackNode;

/*Define o sinônimo para o ponteiro empilhar*/

typedef StackNode *stack;

/*Protótipos*/

void push(stack *Stack,int value);

int pop(stack *Stack);

int isEmpty(stack Stack);

void printStack(stack Stack);

int calculate(int op1, int op2, char operator);

int evaluatePostfixExpression(char *expr);

int main(void){

char postfix[100]="";

char end = '\0';

printf("Enter the expression: ");

scanf("%s",postfix);

/*Adiciona o caractere nulo ao

fim da expressão*/

strncat(postfix,&end,1);

/*Avaliar expressão*/

printf("Result: %d",

evaluatePostfixExpression(postfix));

return 0;

}

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,int value){

StackNode *newNode;

newNode = malloc(sizeof(StackNode));

if(newNode == NULL){

printf("%s not added. Not enough memory");

}else{

/*Adiciona valor ao nó*/

newNode->data = value;

/*Configura o nó para apontar para o topo da pilha*/

newNode->next = *Stack;

/*Novo topo da pilha*/

*Stack = newNode;

}

}

int isEmpty(stack Stack){

return Stack==NULL;

}

int pop(stack *current){

/*Ponteiro de nó temporário*/

stack temp;

int value;

if(isEmpty(*current)){

printf("The stack is empty");

}else{

temp = *current;

value = (*current)->data;

*current = (*current)->next;

free(temp);

}

return value;

}

int calculate(int op1, int op2, char operator){

if(operator =='+'){

return op1 + op2;

}else if(operator =='-'){

return op1 - op2;

}else if(operator =='*'){

return op1 * op2;

}else if(operator =='/'){

return op1 / op2;

}else if(operator =='%'){

return op1 % op2;

}else if(operator =='^'){

int temp = 1;

for(int i = 1; i

temp *= op1;

}

return temp;

}

}

int evaluatePostfixExpression(char *expr){

stack pStack=NULL;

int x,y;

/*Até o final da expressão ser alcançado*/

for(int i = 0; expr[i] !='\0';i++){

if(expr[i]>=48 && expr[i]

/*Se char for digit, push to stack*/

push(&pStack,expr[i]-'0');

}else{

/*Caso contrário, retira dígitos da pilha e

*calcular o resultado. Empurre o resultado

*para a pilha

*/

x = pop(&pStack);

y = pop(&pStack);

push(&pStack,calculate(y,x,expr[i]));

}

}

/*Mostra o resultado final*/

return pop(&pStack);

}

Passo 3

A saída do programa é

Enter the expression: 62+5*84/-

Result: 38

Resposta

Ver o desenvolvimento.