배열로 구현한 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;
}
'1. IT Story > Development' 카테고리의 다른 글
| 큐를 이용한 간단한 구직Pro (0) | 2012.03.29 |
|---|---|
| queueADT를 이용한 간단한 응용프로그램 (0) | 2012.03.29 |
| circularAry 큐를 사용하여 복사하기 (0) | 2012.03.29 |
| StackADT를 이용한 중위식구하기 (0) | 2012.03.29 |
| seqSearch (0) | 2012.03.29 |
| AddressListing (0) | 2012.03.29 |
| 링크드리스트ADT를 이용한 학생성적관리 Pro (0) | 2012.03.29 |
| insertionSort (0) | 2012.03.28 |
운명을바꾸는자
IT와 함께 살아가는 삶
