Postfixation

Data Structure Assignment

* 이 코드만으로는 작동되지 않음.

#pragma once #include "define.h" //이 프로그램에서 사용 될 각종 정의들을 읽어들인다. template <typename T> class CStack //Stack클래스, 다양한 자료형을 지원하기 위해 템플릿 클래스를 사용한다. { //이 Stack은 새로운 노드가 스택의 새로운 시작점이 된다. (List의 입구에서 모든 노드변경이 일어난다) private: tagStack<T>* List; //Stack의 시작점. 템플릿 구조체로 선언되었다. public: CStack(void); ~CStack(void); public: void _Push(T tData); //Stack에 Push할 함수 선언, 템플릿 변수 T의 자료형을 매개변수로 사용한다. T _Pop(); //템플릿 변수를 현재값으로 반환후 해당 Node를 제거하는 Pop함수 T _Top(); //템플릿 변수를 현재값으로 반환하는 Top함수 void _List(); //Stack에 Stack된 자료들을 스택의 Top부터 순서대로 출력한다. }; template <typename T> CStack<T>::CStack() { List = NULL; //생성자에서 스택의 시작부분을 NULL값으로 초기화한다. } template <typename T> CStack<T>::~CStack() { free(List); //소멸자에서 사용한 List를 반환한다. } template <typename T> void CStack<T>::_Push(T tData) { tagStack<T> *Node, *Temp; //Push를 위해 새로운 Node와 임시로 시작잠의 주소를 저장할 Temp변수를 선언한다. Node = new tagStack<T>; //tagStack에 템플릿 자료형을 가지는 새로운 Node를 할당하고, Temp = List; //임시로 사용할 변수 Temp에 현재 리스트의 시작점의 주소를 저장한다. List = Node; //시작점을 새로운 Node로 변경하고 Node->pNext = Temp; //시작점이 된 새로운 Node의 다음 Node로 전의 시작점의 주소를 가져온다. Node->tData = tData; //시작점에 매개변수로 가져온 데이터를 입력한다. } template <typename T> T CStack<T>::_Pop() { if(!List) //만약 리스트가 NULL이라면 NULL값을 반환한다. return NULL; tagStack<T> *Temp; //시작점의 주소를 임시로 저장할 Temp T tValue; //템플릿 자료형의 변수 tValue = List->tData; //현재 시작점의 자료를 템플릿 자료형 변수에 저장하고 Temp = List; //임시 변수에 시작점의 주소를 저장 한 후 List = List->pNext; //시작점을 현재 시작점의 다음 Node로 변경한다. free(Temp); //그 후 Temp에 저장 해두었던 전 시작값의 주소를 반환한다. return tValue; //전 시작값의 자료를 반환한다. } template <typename T> T CStack<T>::_Top() { if(!List) //만약 리스트가 NULL이라면 NULL값을 반환한다/ return NULL; return List->tData; //현재 시작점의 자료를 반환한다. } template <typename T> void CStack<T>::_List() //스택에 쌓여있는 노드들의 자료를 출력한다. { if(!List) //만약 리스트가 NULL이라면 NULL값을 반환한다. { cout << "NULL"; return; } tagStack<T> *Temp = List; //시작점이 변경되면 안됨으로 시작점의 주소값을 임시변수에 복사한다. while(Temp) { cout << Temp->tData; //임시 시작점부터 시작해서 자료를 출력하고 Temp = Temp->pNext; //계속해서 다음의 연결을 찾아간다. } }

#include "Calculation.h" //선언부를 읽어들인다. CCalculation::CCalculation(void) { } CCalculation::~CCalculation(void) //생성자와 소멸자는 사용하지 않았다. { } bool CCalculation::_Run() { bool bCalcAble = true; //연산이 가능한지 확인하는 bool형 변수. __Init(); //사용할 변수들을 할당한다. __Input(); //수식이나 exit를 입력받는다. try //try-catch의 경우 스택으로 메모리를 점유하기도 하고 원래 디버깅용이나, 프로그램의 크기가 작아서 예외처리로 사용한다. { if(!__Check(bCalcAble)) return false; } catch(int except) //_Check함수에서 throw한 값들을 처리한다. { switch(except) //에러의 경우들을 switch문으로 처리한다 { case 1: __Output("Error! 알파벳이 연속으로 입력 되었습니다."); break; case 2: __Output("Error! 수식에 적합하지 않은 문자가 있습니다."); break; case 3: __Output("Error! 수식의 마지막이 숫자나 문자가 아닙니다."); break; case 4: __Output("Error! 괄호의 짝이 맞지 않습니다."); break; case 5: __Output("Error! 연산자가 연속해서 입력 되었습니다."); break; case 6: __Output("Error! 연산자 이후 괄호가 닫혔습니다 (')')."); break; case 7: __Output("Error! 숫자와 알파벳이 연속해서 입력 되었습니다."); break; case 8: __Output("Error! 소수점의 사용이 부적합 합니다."); break; case 9: __Output("Error! 수식의 시작이 연산자 입니다."); break; case 10: //아무것도 입력되지 않았을 경우. 별도의 메시지는 출력하지 않는다. (Run 시퀸스를 빠져나오기 위해 사용) break; default: cout << "Unknown Error! (Error Number : " << except << ")" << endl; //보험 } return true; } __Postfixation(); //__Check함수를 통과했으면 Post-fix를 한다. cout << endl; cout << " *** Input Value : "; __Output(szInputFormula);//입력받은 값을 출력하고, cout << " *** Post Result : "; __Output(szPostFormula); //Post-fix과정이 끝난 결과를 출력한다. if(bCalcAble) //연산이 가능하다면, cout << " *** Calc Result : " << __Calculation() << endl; //연산 하고 결과를 출력한다. cout << endl; __End(); //할당한 변수들을 반환한다. return true; } void CCalculation::__Init() //초기화 함수 { CCalculation::szInputFormula = (char*)malloc(sizeof(char*) * MAXSTRING); //입력받을 수식의 공간을 할당한다. malloc은 C문법이나, 개인적으로 new보다 명시적이라 선호한다. memset(szInputFormula, 0, sizeof(char*) * MAXSTRING); //선언한 공간을 초기화한다. CCalculation::szPostFormula = (char*)malloc(sizeof(char*) * MAXSTRING); //CCalculation::을 변수앞에 써서 변수가 CCalculation에 종속됨을 명시한다. memset(szPostFormula, 0, sizeof(char*) * MAXSTRING); CCalculation::cStack = new CStack<char>; //Postfix에 사용될 스택, char형으로 사용됨을 선언후 할당한다. CCalculation::fStack = new CStack<double>; //계산과정에 사용될 스택, double형으로 사용됨을 선언후 할당한다. } void CCalculation::__End() //소멸자 대응 함수 { free(CCalculation::szInputFormula); free(CCalculation::szPostFormula); free(CCalculation::cStack); free(CCalculation::fStack); } void CCalculation::__Input() { cout << "Input Formula or exit : "; cin.getline(szInputFormula, MAXSTRING); //공백에 관계없이 입력한 전체 문자열을 입력받는다. return; } void CCalculation::__Output(char* szString) { cout << szString << endl; return; } bool CCalculation::__Check(bool &bCalcAble) //bool매개변수는 입력받은 수식이 연산이 가능한가를 나타낸다. { int nBalance = 0, nError = -1, i = 0; //nBalance는 괄호의 적합성 판단에, nError는 각종 잘못된 입력을 판단하는데 사용한다. bool bPoint = false; //bPoint는 소수점의 적합성 판단에 사용한다. if((*szInputFormula == 'e') && (*(szInputFormula+1) == 'x') && (*(szInputFormula+2) == 'i') && (*(szInputFormula+3) == 't')) //종료를 위한 exit 문자열 확인 return false; if(!strlen(szInputFormula)) //아무것도 입력되지 않았을 경우. throw 10; if(strchr("+*/^", *szInputFormula)) //수식의 시작이 -를 제외한 연산자인 경우. throw 9; for(i = 0; *szInputFormula; i++, *szInputFormula++) //입력값의 끝까지 반복한다. { if(*szInputFormula == ' ') //빈공간은 무시한다. continue; else if(isdigit(*szInputFormula)) //현 포인터의 위치의 값이 숫자일 경우 { if(nError == 1) //문자도 수식으로 인정하나, 문자와 숫자가 연속될 경우 에러를 throw한다. throw 7; nError = 0; } else if(isalpha(*szInputFormula)) //현 포인터의 위치의 값이 문자일 경우 { if(nError == 1) //교수님이 말씀하신 조건중 연속된 문자는 처리 하지 않는다고 했음으로 에러를 throw한다. throw 1; else if(nError == 0) //문자와 숫자가 연속됬을 경우 throw. throw 7; nError = 1; bCalcAble = false; //문자가 입력 됬을경우 연산이 불가능하다고 변경한다. } else if(strchr("+-*/^", *szInputFormula)) //현 포인터 위치의 값이 +-*/^중 하나일 경우(연산자일 경우) { if((nError == 5) && (*szInputFormula == '-')) //in-fix에서 연산자가 연속될 일이 없음으로 에러를 throw한다 nError = 6; else if((nError == 5) || (nError == 6)) throw 5; nError = 5; bPoint = false; //숫자의 연속이 끝났음으로 소수점 플래그를 해제한다. } else if(*szInputFormula == '.') { if(nError || !isdigit(*(szInputFormula+1)) || bPoint) //소수점 전의 값이 숫자가 아니거나 후의 값이 숫자가 아니거나 연속된 숫자에서 소수점이 중복 사용됬을 경우 throw 8; //에러를 throw한다. bPoint = true; //연속된 숫자에서 소수점이 사용됬음을 표시한다. } else if(*szInputFormula == '(') //괄호가 열릴 경우 괄호 밸런스를 오른쪽으로 움직인다. nBalance++; else if(*szInputFormula == ')') { if(nError == 5) //연산자 직후에 괄호가 닫히는 경우 올바른 in-fix표현이 아님으로 에러 처리한다. throw 6; nBalance--; //괄호가 닫힐 경우 밸런스를 왼쪽으로 움직인다. } else throw 2; //위의 경우를 제외한 문자는 올바른 입력값이 아님으로 에러 처리한다. if(nBalance < 0) //nBalance가 음수가 됬다는것은 괄호가 열리기 전에 닫혔음을 의미함으로 에러처리한다. throw 4; } if(nBalance) throw 4; //모든 수식을 지난후 밸런스값이 0보다 크다는것은 괄호의 짝이 맞지않음을 의미한다(작을 경우엔 위에서 처리한다) else if(nError > 4) //연산자가 수식의 마지막에 위치 할 경우 처리되는 에러이다. throw 3; szInputFormula = __Rewind(szInputFormula, i); //확인을 마쳤으면 postfixation에서 또 사용 되야 함으로 포인터를 당긴다. return true; } void CCalculation::__Postfixation() { int i = 0, j = 0, nStep = 1, nPreStep = 0; //i는 szinputformula를, j는 szpostformula를 카운팅 한다. (for rewind), nStep, nPreStep은 단계별로 표시하기 위한 변수다. bool bSigned = false; while(*szInputFormula == ' ') { *szInputFormula++; i++; } if(*szInputFormula == '-') { *szPostFormula++ = *szInputFormula++; i++; j++; } for(; *szInputFormula; i++) //공백은 무시한다. { if(*szInputFormula == ' ') { *szInputFormula++; continue; } else if(isalnum(*szInputFormula)) //현 포인터 위치의 값이 숫자나 문자일 경우 { *szPostFormula++ = *szInputFormula; //바로 문자열에 넣는다. j++; bSigned = false; } else if(strchr("+-*/^", *szInputFormula)) //현 포인터 위치의 값이 연산자일 경우 { if((bSigned == false) || (*szInputFormula != '-')) //음수로 판단될 경우가 아닌 경우 { if(*(szPostFormula-1) != ' ') { *szPostFormula++ = ' '; //숫자와 연산자 사이에 공백을 추가한다 j++; } while(cStack->_Top() && (__Priority(cStack->_Top()) >= __Priority(*szInputFormula))) //스택이 존재하고, 스택의 Top의 연산자의 우선순위가 현재 연산자의 우선순위보다 높거나 같다면 계속해서 { *szPostFormula++ = cStack->_Pop(); //뽑아내어 문자열에 추가한다. j++; *szPostFormula++ = ' '; //출력값의 가독성을 위해 연산자 뒤에 공백을 추가한다. j++; } cStack->_Push(*szInputFormula); //그 후 현재 연산자를 스택에 넣는다. bSigned = true; //-가 음수로 판단 될 수 있다는 플래그를 킨다. } else //-가 음수로 판단 될 경우 { *szPostFormula++ = *szInputFormula; //바로 문자열에 넣는다 j++; } } else if(*szInputFormula == '.') //현 포인터 위치의 값이 소수점일 경우 { *szPostFormula++ = '.'; //적합 유무는 Check에서 확인했음으로 바로 문자열에 추가한다. j++; nStep--; } else if(*szInputFormula == '(') //괄호가 열렸을 경우 { cStack->_Push(*szInputFormula); //바로 스택에 추가한다. bSigned = true; } else if(*szInputFormula == ')') //괄호가 닫혔을 경우 { while(cStack->_Top() != '(') //스택의 값이 '('가 나올때까지 { if(*(szPostFormula-1) != ' ') { *szPostFormula++ = ' '; //출력값의 가독성을 위해 연산자 뒤에 공백을 추가한다. j++; } *szPostFormula++ = cStack->_Pop(); //뽑아내어 문자열에 추가한다. j++; *szPostFormula++ = ' '; //출력값의 가독성을 위해 연산자 뒤에 공백을 추가한다. j++; } cStack->_Pop(); //남아있는 '('를 뽑아내어 버린다. } *szInputFormula++; if(nPreStep == nStep) //연속된 숫자의 단계를 제대로 표시하기 위해 필요하다 { nStep++; } else //Post-fix과정을 출력한다. { nPreStep = nStep; //연속 숫자를 표현하기 위해 필요하다. cout << "Step " << nStep++ << " : " << endl << " --- In-Fix : "; // 단계별로 Post-fix과정을 표시한다 cout << szInputFormula << endl << " --- Post-Fix : "; szPostFormula = __Rewind(szPostFormula, j); for(int k = 0; k < j; k++) cout << *szPostFormula++; cout << endl << " --- Stack : "; cStack->_List(); cout << endl; } } //모든 수식을 확인했다. while(cStack->_Top()) //스택의 Top이 NULL이 아닌 동안 { if(*(szPostFormula-1) != ' ') { *szPostFormula++ = ' '; //출력값의 가독성을 위해 연산자 뒤에 공백을 추가한다. j++; } *szPostFormula++ = cStack->_Pop(); //스택에 저장된 값들을 문자열에 추가시킨다. j++; *szPostFormula++ = ' '; //출력값의 가독성을 위해 연산자 뒤에 공백을 추가한다. j++; cout << "Step " << nStep++ << " : " << endl << " --- In-Fix : "; cout << "NONE" << endl << " --- Post-Fix : "; szPostFormula = __Rewind(szPostFormula, j); for(int k = 0; k < j; k++) cout << *szPostFormula++; cout << endl << " --- Stack : "; cStack->_List(); cout << endl; } szPostFormula = __Rewind(szPostFormula, j); //결과 출력을 위해 포인터를 당긴다. szInputFormula = __Rewind(szInputFormula, i); //free시 에러 방지를 위해 포인터를 당긴다. return; } double CCalculation::__Calculation() { int i = 0, j = 0; //rewind를 위한 i, j double fPreOperand, fPostOperand; //in-fix처럼 연산하기 위한 피연산자들 char* szTemp = new char[MAXSTRING]; //연속된 숫자처리를 위해 숫자를 임시로 저장 해 둘 문자열 char cOperator; //연산자 memset(szTemp, 0, MAXSTRING); //초기화 while(*szPostFormula) { if(isdigit(*szPostFormula)) //숫자일 경우 { while(*szPostFormula != ' ') //가독성을 위해 추가했던 공백문자를 Separator로 사용 하였다. { *szTemp++ = *szPostFormula++; //연속된 숫자를 임시 저장공간에 넣고 i++; j++; } szTemp = __Rewind(szTemp, i); //포인터 위치를 당긴후 fStack->_Push(atof(szTemp)); //부동소수형 숫자로 변환하여 스택에 push한다 memset(szTemp, 0, MAXSTRING); //사용한 임시 저장 공간을 비운다. } else if((*szPostFormula == '-') && isdigit(*(szPostFormula+1))) //-기호 바로 뒤가 공백이 아니라 숫자이면 연산자가아닌 signed 기호이다. { while(*szPostFormula != ' ') //가독성을 위해 추가했던 공백문자를 Separator로 사용 하였다. { *szTemp++ = *szPostFormula++; //연속된 숫자를 임시 저장공간에 넣고 i++; j++; } szTemp = __Rewind(szTemp, i); //포인터 위치를 당긴후 fStack->_Push(atof(szTemp)); //부동소수형 숫자로 변환하여 스택에 push한다 memset(szTemp, 0, MAXSTRING); //사용한 임시 저장 공간을 비운다. } else //숫자가 아닐경우 (연산자 일 경우) { cOperator = *szPostFormula++; //연산자를 저장하고 fPostOperand = fStack->_Pop(); //스택에 쌓여있던 숫자 두개를 Pop해온다 fPreOperand = fStack->_Pop(); switch(cOperator) //연산자의 종류에 따라 switch문으로 각기 다르게 연산 { case '+': fStack->_Push(fPreOperand + fPostOperand); //연산 결과를 다시 스택에 Push한다. break; case '-': fStack->_Push(fPreOperand - fPostOperand); break; case '*': fStack->_Push(fPreOperand * fPostOperand); break; case '/': if(fPostOperand == 0) //0으로 나누는 경우 예외적으로 0으로 처리한다. fStack->_Push(0.0f); else fStack->_Push(fPreOperand / fPostOperand); break; case '^': fStack->_Push(pow(fPreOperand, fPostOperand)); break; } j++; } i = 0; //temp rewind매개변수를 초기화 while(*szPostFormula == ' ') { *szPostFormula++; j++; } } free(szTemp); //할당한 임시 저장공간을 반환한다. szPostFormula = __Rewind(szPostFormula, j); return fStack->_Top(); //모든 계산이 끝나고 스택에 남아있는 값이 결과임으로 반환한다. } int CCalculation::__Priority(char Operator) //문자열 우선순위를 반환하는 함수 { switch(Operator) { case '(': //'('은 우선순위가 가장낮다 return 0; case '+': case '-': //+-는 그 다음의 우선순위 return 1; case '*': case '/': //*/은 그 다음의 우선순위 return 2; case '^': //exponent는 우선순위가 가장 높다. return 3; } return -1; //예외처리 } char* CCalculation::__Rewind(char* szSour, int nLength) //문자열을 다시 읽기 위한 함수. { szSour -= nLength; //입력받은 int값만큼 문자열의 포인터를 뒤로 후퇴시킨다. return szSour; //그 후 반환. }