#include "iostream"
#include "math.h"
#include "stdlib.h"
#include "stdio.h"
using namespace std;


//class NÓ
template <class T>
class No
{
private:
No<T>*prox;
T info;


public:
No(T elem, No<T>*p);

T getinfo();
No<T>*getprox();
void setinfo(T);
void setprox(No<T>*p);
};


template <class T>
No<T> :: No(T elem,No<T> *p)
{
info=elem;
prox=p;
}

template <class T>
T No<T> :: getinfo()
{return info;
}

template <class T>
No<T> *No<T> :: getprox()
{return prox;
}

template <class T>
void No<T> :: setinfo(T elem)
{info=elem;
}

template <class T>
void No<T> :: setprox(No<T>*p)
{prox=p;
}






//classe pilha
template <class T>
class pilha
{
private:
No<T> *topo;
int elem;

public:
pilha(void);
void push(T);
int pop(void);
T top (void);
int empty(void);
};

template <class T>
pilha<T> :: pilha()
{topo == NULL;
}

template <class T>
void pilha<T> :: push(T elem)
{No<T> *Novo;
Novo=new No<T>(elem, topo);
topo=Novo;
}

template <class T>
int pilha<T> :: pop()
{No<T> *p;

 if(empty())
 return 0;
 else
 p=topo;
 topo=topo->getprox();
 delete p;
 return 1;
 }

template <class T>
int pilha<T> :: empty()
{if(topo==NULL)
return 1;
else
return 0;
}

template <class T>
T pilha<T> :: top()
{if(!empty())
return topo->getinfo();
}


//prioridade dentro da fila
int Prior1(char c)
{
switch(c)
 {
  case'(':
  return 0;

  case '-':
  return 1;

  case '+':
  return 1;

  case '*':
  return 2;

  case '/':
  return 2;

  case '^':
  return 3;

  }
  }


  //prioridade de chegada na pilha
  int Prior2(char c)
  {
  switch(c)
 {
    case '(':
    return 5;

    case '^':
    return 4;

    case '/':
    return 2;

    case '*':
    return 2;

    case '+':
    return 1;

    case '-':
    return 1;
}
}


//função calculadora
int Calculadora(int a, char simb, int b)
{
switch(simb)
{
 case '+':
 return a+b;

 case '-':
 return a-b;

 case '/':
 return a/b;

 case '*':
 return b*a;

 case '^':
 return (int)pow(a,b);
 }
 }

main()
{
  FILE *CALCULADORA;

  int r, i, j,a,b,c,valida=1;
  char vetor[100],simbolo,t;

  pilha <char> *operador, *P, *aux, *infixa;
  pilha <int> *resultado;

  operador=new pilha<char>;
  P=new pilha<char>;
  aux=new pilha<char>;
  infixa=new pilha<char>;
  resultado= new pilha<int>;

  cout<<"digite sua expressao:"<<endl<<"digite '=' quando terminar"<<endl;
  cin>>simbolo;


//vai verificar se a pilha esta balanceada
  while(simbolo != '=') {

  switch(simbolo){

  case '(':
  P->push(simbolo);
  operador->push(simbolo);
  break;

  case ')':
  if(P->empty())
  valida=0;

  else{
  t=P->top();
  P->pop();

  if((simbolo == ')' && t != '('))
  valida=0;
  }

  break;
  }


  //if vai empilhar na pilha auxiliar (aux) se for operando
  if(simbolo=='0' || simbolo=='1' || simbolo=='2' || simbolo=='3' || simbolo=='4' || simbolo=='5' || simbolo=='6' ||
  simbolo=='7' || simbolo=='8' || simbolo=='9')
  aux->push(simbolo);

  else{

  //se for operador
  switch(simbolo){
  case '+':
  case '*':
  case '/':
  case '-':
  case '(':
  case '^':

  //enquanto a pilha não estiver vazia e a prioridade de chegada for <= que a prioridade de entrada da pilha
  //vai guardar o topo da pilha, remover elemento, inserir na pilha auxiliar
  while(!operador->empty() && Prior2(simbolo)<=Prior1(operador->top())){
  t=operador->top();
  operador->pop();
  aux->push(t);
  }

  operador->push(simbolo);
  break;

  case ')':
  while(!operador->empty() && operador->top() != '('){
  t=operador->top();
  operador->pop();
  aux->push(t);
  }
  operador->pop();
  break;

  }
  }

  cin>>simbolo;
  }//fim do while

  //vai inserir os operadores restantes na pilha auxiliar
  while(!operador->empty()){
  t=operador->top();
  operador->pop();
  aux->push(t);
  }

  if(!P->empty() || !valida){
  cout<<endl<<"expressao nao balanceada"<<endl;

 delete infixa;
 delete operador;
 delete aux;
 delete resultado;
 delete P;
  }


  cout<<endl<<"expressao balanceada"<<endl;

  while(!aux->empty()){
  t=aux->top();
  infixa->push(t);
  aux->pop();
  }

 //teste de while
 while(!resultado->empty()){
 resultado->pop();}

  i=0;
  while(!infixa->empty()){
  simbolo=infixa->top();
  vetor[i]=simbolo;
  i++;

  if(simbolo=='0' || simbolo=='1' || simbolo=='2' || simbolo=='3' || simbolo=='4' || simbolo=='5' || simbolo=='6' ||
  simbolo=='7' || simbolo=='8' || simbolo=='9'){
  //passa pra inteiro
  a=atoi(&simbolo);
  resultado->push(a);
  }

  //simbolo é operador
  //joga simbolo na variavel t, pega o proximo numero da fila infixa junto com o topo da pilha resultado e efetua o calculo
  else{
  t=simbolo;
  b=resultado->top();
  resultado->pop();

  infixa->pop();
  simbolo=infixa->top();

  a=atoi(&simbolo);

  c=Calculadora(a, t, b);
  resultado->push(c);
  }
  infixa->pop();
  }
  r=resultado->top();
  cout<<endl<<"resultado da operacao: "<<r<<endl;

  delete infixa;
  delete operador;
  delete aux;
  delete resultado;
  delete P;

  //arquivo .txt
  CALCULADORA=fopen("CALCULADORA.txt", "w");
  fprintf(CALCULADORA, "expresao balanceada \n");
  fprintf(CALCULADORA, "resposta = %d", r);
  fprintf(CALCULADORA, "\n \n");
  fclose(CALCULADORA);

  system("pause=0");

  }