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.