Material didático para princípios de desenvolvimento de Algoritmos

LinhaCodigo
001// Prof. Leo^nidas - http://www.matematica.br http://line.ime.usp.br
002// MAC0122 - 2017/10/08
003
004// Descricao: Transforma uma expressao aritmetica em outra equivalente em notacao pos-fixada
005//            notacao in-fixa  : EXP op EXP
006//            notacao pos-fixa : EXP EXP op
007// Interessante: a notacao pos-fixa dispensa parenteses! E.g. "(2+3)*4" fica como "2 3 + 4 *"
008
009// Ideia: Usar uma pilha apenas para operadores, a cada operando anotar na "pilha final"
010//  1. Para cada caractere da expressao de entrada (notacao in-fixa e usando uma unica letra) - lendo da esquerda para a direita a "string"
011//  2.   Se caractere e' operando, insira na expressao pos-fixada 
012//  3.   Senao
013//  4.   Se caractere e' '(', entao empilhe-o
014//  5.   Senao
015//  6.   Se caractere e' ')', entao desempilhe e insira-o na expressao pos-fixada, ate' encontrar '('
016//  7.   Senao
017//  8.   Enquanto a pilha nao vazia e precedencia do operador atual <= precedencia do operador no topo da pilha, 
018//  9.     desempilhe e insira-o na expressao pos-fixada
019// 10.     empilhe operador atual
020// 11. Desempilhe os operadores que restaram na pilha de operadores, inserindo cada um na expressao pos-fixada e na "pilha final"
021
022#include <stdio.h>
023#include <string.h>
024#include <stdlib.h>
025
026#define MAX 256
027#define DEBUG 0
028
029// Construtor do tipo "pilha"
030typedef struct {
031  int topo;
032  unsigned comprimentoPilha;
033  int * dadosPilha;
034  } tipoPilha;
035
036// Estrutura registrando a pilha (usar uma para operadores e uma para a expressao em notacao pos-fixa)
037tipoPilha * criarPilha (unsigned comprimento) {
038  tipoPilha * pilha = (tipoPilha*) malloc(sizeof(tipoPilha));
039  if (!pilha)
040    return NULL;
041  pilha->topo = -1;
042  pilha->comprimentoPilha = comprimento;
043  pilha->dadosPilha = (int*) malloc(comprimento * sizeof(int));
044  if (!pilha->dadosPilha)
045    return NULL;
046  return pilha;
047  }
048
049// Verifica se caractere e' operando (simplificacao: aceito apenas 'a' ate 'z' ou 'A' ate 'Z'
050int ehOperando (char ch) {
051  return (ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z');
052  }
053
054// Devolve a precedencia de operador (se operador, senao -1): ^ => 2; * / => 1; + 0 => 0
055int ordemPrecedencia (char ch) {
056  switch (ch) {
057    case '+':  case '-': return 0;
058    case '*':  case '/': return 1;
059    case '^':            return 2;
060    }
061  return -1;
062  }
063
064void examinaPilha (int *vetor, int comp) { // examine pilha de 0 ate o topo = 'comp'
065  int i;
066  if (DEBUG) printf("Examina pilha de operadores: #pilha = %d\n ", comp);
067  for (i=0; i<=comp; i++) {
068    printf("%c, ", vetor[i]);
069    }
070  printf("\n");
071  }
072
073int pilhaVazia (tipoPilha* pilha) { // create
074  return (pilha->topo == -1);
075  }
076char examinaTopoPilha (tipoPilha* pilha) { // examina
077  //S if (pilha==NULL || pilha->topo==-1) { printf("examinaTopoPilha: pilha vazia! topo=%d\n", pilha->topo); return 255; } // pilha vazia => devolva maior ASCII
078  return pilha->dadosPilha[pilha->topo];
079  }
080char desempilha (tipoPilha* pilha) { // desempilha
081  if (!pilhaVazia(pilha))
082    return pilha->dadosPilha[pilha->topo--] ;
083  return '$';
084  }
085void empilha (tipoPilha *pilha, char c, int aux) { // empilhe
086  if (c == ' ') { printf("empilha: ERRO branco! topo=%d\n", pilha->topo); return; }
087  pilha->dadosPilha[++pilha->topo] = c;
088  if (DEBUG) printf(" (%d: %d) c=%c ", aux, pilha->topo, c);
089  }
090
091// Insere operando ou operador para compor uma pilha completa em notacao pos-fixada
092void insereItemExp (char *str, char c, int *k, tipoPilha *pilha) {
093  if (c == ' ') return;
094  str[++*k] = c;
095  empilha(pilha, c, 3); 
096  }
097
098// Converte um expressao composta por operadores com uma unica letra (em notacao in-fixa) em equivalente pos-fixa
099int infixa2PosFixada (char* strExpIn, char* strExpPos, tipoPilha **pilhaOriginal, tipoPilha **pilhaFinal) {
100  tipoPilha *pilha, *pilhaAux; // apenas para eliminar um apontamento '*'
101  int i, k; char c;
102
103  // Cria pilha usando vetor, de tamanho comprimentoPilha igual ao tamanho da expressao
104  pilha = criarPilha(strlen(strExpIn));    // esta sera' a "pilha de operadores"
105  pilhaAux = criarPilha(strlen(strExpIn)); // esta sera' a "pilha final" (com elementos na ordem da notacao pos-fixa)
106  *pilhaOriginal = pilha;
107  if (DEBUG) printf("infixa2PosFixada: pilhaOriginal->comprimentoPilha=%d\n", (*pilhaOriginal)->comprimentoPilha);
108
109  for (i = 0, k = -1; strExpIn[i]; i++) { // Examina cada caractere (item lexico)
110    c = strExpIn[i];
111    if (ehOperando(c)) { // Caractere atual e' operando: solte-o
112      insereItemExp(strExpPos, c, &k, pilhaAux); // Insere na "pilha final" e na expressao pos-fixa
113      }
114    else
115    if (c == '(') { // Caractere atual e' '(': empilhe-o
116      empilha(pilha, c, 1);
117      if (DEBUG) { printf("empilha: "); examinaPilha(pilha->dadosPilha, pilha->topo); }
118      }
119    else
120    if (c == ')') { // Caractere atual e' ')': desempilha e desempilhe ate encontrar um '('
121      while (!pilhaVazia(pilha) && examinaTopoPilha(pilha) != '(') {
122        insereItemExp(strExpPos, desempilha(pilha), &k, pilhaAux); // Insere na "pilha final" e na expressao pos-fixa
123        if (DEBUG) { printf("desempilha: "); examinaPilha(pilha->dadosPilha, pilha->topo); }
124        }
125      if (!pilhaVazia(pilha) && examinaTopoPilha(pilha) != '(')
126        return -1; // expressao invalida!?
127      else {
128        desempilha(pilha);
129        if (DEBUG) { printf("desempilha: "); examinaPilha(pilha->dadosPilha, pilha->topo); }
130        }
131      } // if (c == ')')
132    else { // Caractere atual e' operador: desempilhe enquanto precedencia dele for menor que do topo da pilha
133      while (!pilhaVazia(pilha) && ordemPrecedencia(c) <= ordemPrecedencia(examinaTopoPilha(pilha))) {
134        insereItemExp(strExpPos, desempilha(pilha), &k, pilhaAux); // Insere na "pilha final" e na expressao pos-fixa
135        if (DEBUG) { printf("desempilha: "); examinaPilha(pilha->dadosPilha, pilha->topo); }
136        }
137      empilha(pilha, c, 2);
138      if (DEBUG) { printf("empilha: "); examinaPilha(pilha->dadosPilha, pilha->topo); }
139      }
140    } // for (i = 0, k = -1; strExpIn[i]; i++)
141
142  if (DEBUG) { printf("O que sobou na pilha k=%d: ", k); examinaPilha(pilha->dadosPilha, pilha->topo); }
143
144  // desempilha todos os operadores que sobraram na pilha
145  while (!pilhaVazia(pilha)) {
146    insereItemExp(strExpPos, c = desempilha(pilha), &k, pilhaAux); // Insere na "pilha final" e na expressao pos-fixa
147    if (DEBUG) { printf(" insere %d, k=%d: %c\n", pilha->topo, k, c); }
148    }
149  strExpPos[++k] = '\0'; // Finaliza "string" da expressao em notacao pos-fixa
150  pilhaAux->comprimentoPilha = k; // Agora temos o tamanho da expressao em 'pos-fixa' (sem os parenteses)
151
152  *pilhaFinal = pilhaAux; // Pilha final
153
154  } // int infixa2PosFixada(char* strExpIn, char* strExpPos, tipoPilha **pilhaOriginal, tipoPilha **pilhaFinal)
155
156// Programa principal
157int main () {
158  tipoPilha *pilha, *pilhaFinal;
159  char strExpPos[MAX]; // Para a expressao final em notacao pos-fixa
160  int i;
161  char *strExp,
162    strExpressao[][MAX] = { // Exemplos fixos
163      "a+b*c",
164      "(a+b)*c",
165      "a+b*c^d",
166      "a+b*c^d-e",
167      "a+b*c^d-e*f",
168      "a+b*c^d-e*f+g",
169      "a+b*c^d-e*f+g-h",
170      "a+b*c^d-e*f+g-h/i",
171      "a+(b*c)^d-e*f+g-h/i",
172      "a+(b*c)^(d-e)*f+g-h/i" 
173     };
174
175  for (i=0; i<10; i++) {
176    //printf("Digite uma expressao em notacao in-fixa: "); //D Se desejar digitar...
177    //scanf("%s", strExp);
178    strExp = strExpressao[i];
179    infixa2PosFixada(strExp, strExpPos, &pilha, &pilhaFinal);
180 
181    printf("Expressao original: %s\n", strExp);
182    printf("Expressao final   : %s\n", strExpPos);
183
184    printf("                  : ");
185    examinaPilha(pilhaFinal->dadosPilha, pilhaFinal->topo);
186    }
187  printf("\n");
188
189  return 0;
190  }