스택 기반 수식 계산기 / 중위식 변환 (Expression Evaluation based stack / Convert Infix Expression to Postfix & Prefix Expression)

* input sample

10
2+4*5-3
(2+4)*(5-3)
2-5*3+1
2-5*3+1
5/3
2-5*3+1
2-5*3+1
2-5*3+1
2-5*3+1
2-5*3+1

* output sample

10

Expression (1/10)
Infix: 2+4*5-3
Postfix: 245*+3-
Result: 19
Infix: ((2+(4*5))-3)

Expression (2/10)
Infix: (2+4)*(5-3)
Postfix: 24+53-*
Result: 12
Infix: ((2+4)*(5-3))

Expression (3/10)
Infix: 2-5*3+1
Postfix: 253*-1+
Result: -12
Infix: ((2-(5*3))+1)

Expression (4/10)
Infix: 2-5*3+1
Postfix: 253*-1+
Result: -12
Infix: ((2-(5*3))+1)

Expression (5/10)
Infix: 5/3
Postfix: 53/
Result: 1.66667
Infix: (5/3)

Expression (6/10)
Infix: 2-5*3+1
Postfix: 253*-1+
Result: -12
Infix: ((2-(5*3))+1)

Expression (7/10)
Infix: 2-5*3+1
Postfix: 253*-1+
Result: -12
Infix: ((2-(5*3))+1)

Expression (8/10)
Infix: 2-5*3+1
Postfix: 253*-1+
Result: -12
Infix: ((2-(5*3))+1)

Expression (9/10)
Infix: 2-5*3+1
Postfix: 253*-1+
Result: -12
Infix: ((2-(5*3))+1)

Expression (10/10)
Infix: 2-5*3+1
Postfix: 253*-1+
Result: -12
Infix: ((2-(5*3))+1)




main.cpp

// Expression Evaluation
#include "Calc.h"

int main()
{


 try
 {

  Calc* test;

  char exp[11][MAX_CHAR];
  int i,j,k;
 
  for(i=0;i<11;i++)
   for(j=0;j<MAX_CHAR;j++)
    exp[i][j]=NULL;

 
  ifstream file1;
  file1.open("input.txt");
 
  i=0;k=0;
  while(file1)
  {
   if(i>=11) break;
   file1.getline(exp[i],MAX_CHAR);
   
   i++;
  }
  file1.close();
  
  ofstream file2;
  file2.open("output.txt");
 
  k=0;
 
  for(j=0;j<=i;j++)
  {
   if(exp[j][0]==NULL||exp[j][0]=='\n') // NULL expression
   {
    i--;
   }
   else if((exp[j][1]==NULL||exp[j][1]=='\n')||(exp[j][2]==NULL||exp[j][2]=='\n')) // a number
   {
    i--;
   }  
  }

  for(j=0;j<=i;j++)
  {
   if((exp[j][1]==NULL||exp[j][1]=='\n')||(exp[j][2]==NULL||exp[j][2]=='\n')) // a number 
   {
   file2 << exp[j] << endl << endl;
   continue; 
   }


   test = new Calc(INFIX,exp[j]); // INFIX expression
   file2 << "Expression (" << k+1 << "/" << i << ")" << endl
    << "Infix:  " << test->PrintExp() << endl;
     
   test->Convert(POSTFIX);
   file2 << "Postfix: " << test->PrintExp() << endl;
   file2 << "Result:  " << test->Evaluate() << endl;

   test->Convert(INFIX);
   file2 << "Infix:  " << test->PrintExp() << endl << endl;

   delete test;
   k++;
  }

  file2.close();

  cout << "Please open output.txt" << endl;

 }
 catch(char* e)
 {
  cout << e << endl;
 }


 return 0;

}

Calc.h

// Calc.h
#ifndef CALC_H
#define CALC_H

#define INFIX 0
#define POSTFIX 1

#define MAX_CHAR 100 // maximum size of the expression

#include <iostream> 
#include <stack> // use class stack<T>
#include <fstream> // use class ifstream, ofstream

using namespace std;

class Calc
{
private:
 
 int type; // INFIX or POSTFIX
 char* expression; // ex) 2+3*4 , 234*+, (2+(3*4))

public:
 Calc(int n_type,char* n_exp); // n_type: type of expression , n_exp: new expression line
 // Because array of expressions is static array, this class has default destructor.

 void Convert(int c_type); // ex) Convert(INFIX): if type==POSTFIX, convert POSTFIX to INFIX.
 double Evaluate(); // evaluate the expression
 char* PrintExp(); // return pointer of the expression

};



#endif

Calc.cpp

//Calc.cpp
#include "Calc.h"

Calc::Calc(int n_type,char* n_exp) // Constructor
{

 type = n_type;
 expression = n_exp;

}

void Calc::Convert(int c_type)
{
 char* t_exp;
 t_exp = new char[MAX_CHAR]; // temporary expression initialize
 for(int i=0;i<MAX_CHAR;i++)
  t_exp[i]=NULL;

 int i=0,j=0;

 if(c_type == type) // do not need to convert
  return;
 
 if(c_type == INFIX) // convert POSTFIX to INFIX
 {
  stack<char> p;
  stack<char> t1,t2;
  while(expression[i]!=NULL)
  {
   if(expression[i] >= '0' && expression[i] <= '9') // is it operand?
   {
    p.push(expression[i]);
   }
   else if (expression[i]=='+'||expression[i]=='-'||expression[i]=='*'||expression[i]=='/'||expression[i]=='%') // is it operator?
   {
    do
    {
     if(p.top()==')')
      j++;
     if(p.top()=='(')
      j--;
     t2.push(p.top());
     p.pop();   
    }while(j);

    do
    {
     if(p.top()==')')
      j++;
     if(p.top()=='(')
      j--;
     t1.push(p.top());
     p.pop();   
    }while(j);

    p.push('(');
    while(!t1.empty())
    {
     p.push(t1.top());
     t1.pop();
    }
    p.push(expression[i]);
    while(!t2.empty())
    {
     p.push(t2.top());
     t2.pop();
    }
    p.push(')');

   }
   else if(expression[i] == ' ') // is it blank?
   {
   }
   else // unknown operator
   {
    throw "Error : Not allowed operator. (Calc::Convert(INFIX))";;
   }

   i++;


  }


  // load t_exp from stack p
  for(i=p.size()-1;!p.empty();i--)
  {
   t_exp[i] = p.top();
   p.pop();
  }



  //delete expression;
  expression = t_exp;
  type = INFIX;

  //cout << expression << endl;

  return ;

 }

 if(c_type == POSTFIX) // convert INFIX to POSTFIX
 {
  stack<char> t;
  while(expression[i]!=NULL)
  {
   if(expression[i] >= '0'&&expression[i] <='9') // is it operand?
   {
    t_exp[j] = expression[i];
    j++;
   }
   else if(expression[i] == '*'||expression[i] == '/'||expression[i] == '%') // higher priority operator
   {
    t.push(expression[i]);
   }
   else if(expression[i] == '+'||expression[i] == '-') // lower priority operator
   {
    while(!t.empty())
    {
     if(t.top()=='(')
      break;

     t_exp[j] = t.top();
     j++;
     t.pop();

     if(t_exp[j]=='+'||t_exp[j]=='-')
      break;
    }
    
    t.push(expression[i]);
   }
   else if(expression[i] == '(') // opened bracket
   {
    t.push(expression[i]);
   }
   else if(expression[i] == ')') // closed bracket
   {

    while(!t.empty())
    {
     if(t.top()=='(')
     {
      t.pop();
      break;
     }

     t_exp[j] = t.top();
     j++;
     t.pop();
    }
   }
   else if(expression[i] == ' ') // is it blank?
   {
   }
   else 
   {
    throw "Error : Not allowed operator. (Calc::void Convert(POSTFIX))";
   }

   i++;
  }

  while(!t.empty())
  {
   t_exp[j] = t.top();
   j++;
   t.pop();
  }


  //delete expression;
  expression = t_exp;
  type = POSTFIX;

  return;
 }

 throw "Error : There is an unknown type. (private:int type;void Calc::Convert(???))";

}

double Calc::Evaluate()
{
 if(type == INFIX)
 {
  this->Convert(POSTFIX);
  return this->Evaluate();
 }
 
 if(type == POSTFIX)
 { 
  int i=0;
  double answer,temp;
  stack<double> t;
  while(expression[i]!=NULL)
  {
   if(expression[i]>='0' && expression[i]<='9')
   {   
    t.push(expression[i]-'0');
   
   }
   else
   {
    temp = t.top();
    t.pop();
    switch(expression[i])
    {
    case '+':
     temp = t.top() + temp;
     break;
    case '-':
     temp = t.top() - temp;
     break;
    case '*':
     temp = t.top() * temp;
     break;
    case '/':
     temp = t.top() / temp;
     break;
    case '%':
     temp = static_cast<int>(t.top()) % static_cast<int>(temp);
     break;
    }
    //if(!t.empty())
     t.pop();

    t.push(temp);
   }

   i++;
  }

  answer = t.top();
  
 // this->Convert(INFIX);
 // cout << expression << " = "
 //  << answer << endl;
  
  return answer;
 }
 
  
 throw "Error : There is an unknown type. (private:int type;int Calc::Evaluate())";

 
}

char* Calc::PrintExp()
{
 return expression;
}