StackADT를 이용한 중위식구하기

 

StackADT를 이용한 중위식구하기

 

StackADT.h

template<typename TYPE>

struct Node
{
  TYPE data;
  Node<TYPE>* next;
};

template<typename TYPE>

class Stack
{
private:
  int count;
  Node<TYPE>* top;
 
public:
  Stack();
  ~Stack();
  bool pushStack(TYPE dataIn);
  bool popStack(TYPE& dataOut);
  bool stackTop(TYPE& dataOut);
  bool emptyStack();
  bool fullStack();
  int stackCount();

};

template<typename TYPE>

Stack<TYPE>:: Stack()
{
 top=NULL;
 count=0;

}

template<typename TYPE>

Stack<TYPE>:: ~Stack()
{
 Node<TYPE>* temp;

 while(top != NULL)
 {
  temp= top;
  top = top->next;
  delete temp;
 }

 count = 0;

}

 

template<typename TYPE>

bool Stack<TYPE>::pushStack(TYPE dataIn)
 {
    bool success;
 Node<TYPE>* newPtr;

 newPtr = new  Node<TYPE>;

  if(newPtr==NULL)
  {
    success= false;
  }
  else
  {
   newPtr->data = dataIn;
   newPtr->next = top;
   top= newPtr;
   count++;

         success = true;
  }
  return success;
 
 
 }

template<typename TYPE>

bool Stack<TYPE>::popStack(TYPE& dataOut)
 {
    bool success;
 Node<TYPE>* dltPtr;

  if(count==0)
  {
    success= false;
  }
  else
  {
   dltPtr=top;
   dataOut=top->data;
   top=top->next;
   count=count-1;
   delete dltPtr;
   success = true;
  
  
  
         success = true;
  }
  return success;
 
 
 }

 

template<typename TYPE>
bool Stack<TYPE> :: stackTop(TYPE& dataOut)
{
   bool success;
   Node<TYPE>* dltPtr;

   if(count==0)
   {
    success = false;
  
   }
   else
   {
    dltPtr = top;
    dataOut = top->data;
    top= top->next;
    count--;
    delete dltPtr;
    success = true;
   }
   return success;

}

template<typename TYPE>

int Stack<TYPE> :: stackCount()
{

 return count;

}
template<typename TYPE>
bool Stack<TYPE> :: fullStack()
{
 bool success;
 Node<TYPE>* tt;

 tt= new Node<TYPE>;
 
 if(tt==NULL)
 {
  success = false;
 }
 else
 {
  delete tt;
  success = true;
 }
 return success;

}

//스택이 비어 있으면 return true를 한다.

template<typename TYPE>
bool Stack<TYPE>:: emptyStack()
{

 return (count== 0);

}

 

main.cpp

#include <iostream>
#include <iomanip> 

#include "StackADT.h"
#include <string>
using namespace std;

int priority(char c);
char postFixEval(char* postfix);
int calculate(int op1, int op2, char c);

int main()
{
 Stack<char> stack;

 char infix[100];
 char postfix[100];

 cout<<"중위식입력: ";
 cin.getline(infix, sizeof(infix));
 
 int len = strlen(infix);
 char c;
 char token,topToken;
 int j=0;
 

 for(int i=0; i<len; i++)
 {
   c=infix[i];
   cout<< c <<endl;

  
   if(c==' ')
   {
    // do nothing;
  
   }
   else if(c=='(')//여는 괄호
   {
   stack.pushStack(c);
  
   }
   else if(c==')') //닫는괄호
   {
   stack.popStack(token);
   cout<< token<< endl;

   while(token!='(')
   {
    postfix[j] = token;

 j++;
 stack.popStack(token);
   }

   }//else if(c==')') //닫는괄호
   else if(c=='+' || c=='-' || c=='*' || c=='/') //연산자
   {
    stack.stackTop(topToken);
   
    while( !(stack.emptyStack()) && ( priority(c) <= priority(topToken) ))
    {
     stack.popStack(token);
     postfix[j]=token;
     j++;

     stack.stackTop(topToken);
    }
    stack.pushStack(c);
   }//else if(c==) //연산자
   else //피연산자
    {
    postfix[j]=c;
 j++;
  
   }//피연산자
 }//for

 while(!(stack.emptyStack())) // 스택비우기
 {
  stack.popStack(token);
  postfix[j]=token;
  j++;
 }
 postfix[j]='\0';
 cout << postfix <<endl;

int d= postFixEval(postfix);

cout<<"계산값: " << d <<endl;
   return 0;
}

int priority(char c)
{

int p;

 if( (c=='('))
 {
  p=0;
 
 }
 else if(c=='+' || c=='-' )
 {
 p=1;
 
 }
 else if(c=='*' || c=='/')
 {
 p=2;
 }
 return p;

}

char postFixEval(char* postfix)
{
 Stack<int> stack;
 int exprSize= strlen(postfix);
 char c;
 int op1,op2;
 int num;

 for(int index=0; index<exprSize; index++)
 {
  c=postfix[index];

  if(c=='+' || c=='-' || c=='*' || c=='/')// 4개의 연산자
  {
   stack.popStack(op1);
   stack.popStack(op2);
 
   int value = calculate(op1, op2, c);
   stack.pushStack(value);
 
 
  }//if()// 4개의 연산자
 
  else // 피연산자
  {
  int a=c-48;
  stack.pushStack(a);

  //문자 4의 아스키코드값=52
  //52-48=4 -> 숫자 4로 변환됨
  }//else 피연산자

 }//for 스택에 집어 넣는 작업
 int result;
 stack.popStack(result);

 return result;

}

int calculate(int op1, int op2, char c)
{
  int res;

  if(c=='+')
  {
   res= op1+op2;
 
  }
  else if(c=='-')
  {
   res= op1-op2;
 
  }
  else if(c=='*')
  {
   res= op1*op2;
 
  }
  else if(c=='/')
  {
   res= op1/op2;
  }
  else
  {
   return 00;
  }

  return res;

}