배열로 구현한 Stack을 이용한 중위식구하기

 

배열로 구현한 Stack을 이용한 중위식구하기

 

StackAry.h

template<typename TYPE>
struct NODE
{
 TYPE data;
};

template<typename TYPE>
class Stack
{
private :
    NODE<TYPE>* stackAry;
 int count;
 int stackMax;
 int top;

public:
 Stack(int size = 100);
 ~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(int size = 100)
{
 stackMax = size;
 stackAry = new NODE<TYPE> [stackMax];
 
 if(!stackAry)
 {
  cout<< "메모리 넘침"<<endl;
  abort();
 }
 count=0;
 top=-1;
}

template<typename TYPE>
Stack<TYPE>::~Stack()
{
 delete [] stackAry;

}

template<typename TYPE>
bool Stack<TYPE> :: pushStack(TYPE dataIn)
{
 if(count >=stackMax)
 {
 return false;
 }
 count++;
 top++;
 stackAry[top].data=dataIn;
 return true;

}

template<typename TYPE>
bool Stack<TYPE> :: popStack(TYPE& dataOut)
{
  bool success;

  if(count==0)
  {
   success = false;
  }
  else
  {
  
  dataOut = stackAry[top].data;
  top--;
  count--;
  success = true;
  
  }
  return success;

}

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

 if(count==0)
 {
  success = false;
 }
 else
 {
  dataOut = stackAry[top].data;
  success = true;
 }
 return success;
}

template<typename TYPE>
bool Stack<TYPE> ::  emptyStack ()
{
 return (count == 0); // true // false

}

template<typename TYPE>
bool Stack<TYPE> ::  fullStack()
{
 return (count == stackMax);
}

template<typename TYPE>
int Stack<TYPE> :: stackCount()
{
  return count;
}

 

main.cpp

#include <iostream>
#include <iomanip> 
#include <string>
#include "StackAry.h"

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;

 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;

}