Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdlib.h>
- #include <stdio.h>
- #include <string.h>
- #include <ctype.h>
- typedef struct tarvore{
- char *c;
- struct tarvore *esquerda, *direita;
- }arvore;
- typedef struct tpilha{
- char letra;
- struct tpilha *proximo;
- }pilha;
- pilha *empilharcaracter(char caracter){
- pilha *auxiliar=NULL;
- auxiliar = (pilha*)malloc(sizeof(pilha));
- auxiliar->letra = caracter;
- return auxiliar;
- }
- void empilha(pilha **topo, pilha *novo){
- novo->proximo = *topo;
- *topo = novo;
- }
- char desempilhar(pilha **topo){
- pilha *aux=NULL;
- aux = *topo;
- *topo = (*topo)->proximo;
- return aux->letra;
- }
- void insereArvore(arvore **raiz, char *str, int &i){
- char letra;
- if(i>=0){
- letra = str[i--];
- *raiz = (arvore*)malloc(sizeof(arvore));
- if(letra=='.'){
- (*raiz)->c = (char*)malloc(sizeof(char)*((int)str[i]-47));
- (*raiz)->c[(int)str[i]-48] = '\0';
- for(int j=(int)str[i]-49;j>=0;j--){
- i--;
- (*raiz)->c[j] = str[i];
- }
- i--;
- }
- else{
- (*raiz)->c = (char*)malloc(sizeof(char));
- (*raiz)->c[0] = letra;
- }
- if(letra=='+' || letra=='-' || letra=='*' || letra=='/'){
- insereArvore(&(*raiz)->direita, str, i);
- insereArvore(&(*raiz)->esquerda, str, i);
- }
- else{
- (*raiz)->esquerda = NULL;
- (*raiz)->direita = NULL;
- }
- }
- }
- void anularTopo(pilha **topo){
- pilha *aux=*topo;
- (*topo) = (*topo)->proximo;
- free(aux);
- }
- void notacaoPolonesa(pilha **topo, char *str, int &tamanho){
- int j, k=0, l=0;
- char temp[tamanho];
- for(j=0;str[j]!='\0';j++){
- if(isdigit(str[j])){
- temp[k++] = str[j];
- l++;
- if(l>1 && !isdigit(str[j+1])){
- tamanho+=2;
- realloc(temp, tamanho);
- temp[k++] = (char)(l+48);
- temp[k++] = '.';
- }
- }
- else{
- if(*topo==NULL){
- empilha(topo, empilharcaracter(str[j]));
- }
- else{
- if(str[j]=='('){
- empilha(topo, empilharcaracter(str[j]));
- }
- else if(((*topo)->letra=='*' || (*topo)->letra=='/') && (str[j]=='+' || str[j]=='-')){
- temp[k++] = desempilhar(topo);
- empilha(topo, empilharcaracter(str[j]));
- }
- else if(((*topo)->letra=='+' || (*topo)->letra=='-' || (*topo)->letra=='*' || (*topo)->letra=='/' || (*topo)->letra=='(') && (str[j]=='/' || str[j]=='*' || str[j]=='+' || str[j]=='-')){
- empilha(topo, empilharcaracter(str[j]));
- }
- else{
- while((*topo)->letra!='('){
- temp[k++] = desempilhar(topo);
- }
- anularTopo(topo);
- }
- }
- l=0;
- }
- }
- while((*topo)!=NULL){
- temp[k++] = desempilhar(topo);
- }
- temp[k++] = '\0';
- strcpy(str, temp);
- free(temp);
- }
- int calcularArvore(arvore *raiz){
- if(raiz->c[0]=='+')
- return calcularArvore(raiz->esquerda) + calcularArvore(raiz->direita);
- if(raiz->c[0]=='-')
- return calcularArvore(raiz->esquerda) - calcularArvore(raiz->direita);
- if(raiz->c[0]=='*')
- return calcularArvore(raiz->esquerda) * calcularArvore(raiz->direita);
- if(raiz->c[0]=='/')
- return calcularArvore(raiz->esquerda) / calcularArvore(raiz->direita);
- return atoi(raiz->c);
- }
- int procurarParenteses(char *str){
- int j, c=0, tam;
- for(j=0;str[j]!='\0';j++){
- if(str[j]=='(')
- c+=2;
- }
- tam = strlen(str)-c-1;
- return tam;
- }
- void expressao(char *str){
- printf("Exp: ");
- scanf("%s", str);
- }
- int main(void){
- arvore *raiz=NULL;
- pilha *topo=NULL;
- int i;
- char str[100];
- expressao(str);
- i = procurarParenteses(str);
- notacaoPolonesa(&topo, str, i);
- insereArvore(&raiz, str, i);
- printf("\nResultado: %d", calcularArvore(raiz));
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement