9.3 수식 파서 트리(Numeric Parser Tree)
수식 계산기는 스택으로 만드는 방법과 파서 트리로 만드는 방법이 있습니다. 정규화를 할 수 있는 구문을 파싱(Parsing)할 때 파서 트리로 구현하면 운행 방법에 따라 원하는 결과물을 얻을 수 있습니다.
이번에는 컴파일러 개념을 도입한 수식 파서 트리를 만들어 보기로 할게요.
파서(Parser)는 파싱하는 도구를 말합니다. 그리고 파싱은 입력 문장을 분석하는 것을 말합니다. 따라서 파서는 입력 문장을 분석하여 원하는 결과물을 만드는 번역기라 할 수 있습니다. 컴파일러도 고급 언어로 작성한 소스를 분석하여 기계어로 번역하므로 내부에 파싱하는 파서가 필요합니다.
컴파일러가 컴파일하는 과정은 여러 단계로 나누며 컴파일러 종류에 따라 다릅니다. 여기에서는 공통적으로 수행해야 하는 과정을 소개하고 이를 수식 파서 트리에 도입해서 구현해 볼게요.
컴파일러는 어휘 분석(Lexical) → 구문 분석(Syntax) → 의미 분석(Semantic) → 파싱(Parsing) → 중간 코드 생성 (Midi Code Generation) 과정을 거칩니다. 컴파일러에 따라 최적화(Optimization) 과정을 거칠 수도 있으며 각 과정을 반복해서 수행하기도 합니다.
어휘 분석(Lexical) 단계는 입력 문장에 의미있는 최소 단위인 토큰(Token)을 만드는 과정으로 토큰 생성기에서 수행합니다. 만약 사용할 수 없는 토큰을 발견하면 오류로 처리합니다. 예를 들어 수식 파서 트리에 입력한 문장 “23-5*9”이 들어오면 “23”, “-“, “5”, “*”, “9”를 토큰으로 만듭니다. “23-5#9”가 들어오면 수식에 사용할 수 없는 “#”가 있어서 오류가 발생합니다.
구문 분석(Syntax)에서는 토큰의 배치가 문법에 맞게 배치하였는지 확인하며 구문 분석기에서 수행합니다. 만약 배치 순서에 문제가 있으면 오류로 처리합니다. 예를 들어 “23-5*9”는 토큰 순서가 수식 문법에 맞습니다. 하지만 “23-5*/7”은 토큰 순서가 수식 문법에 맞지 않아 오류가 발생합니다.
의미 분석(Semantic)에서는 자료 형식이 논리에 맞는지 확인하며 의미 분석기에서 수행합니다. 형식에 맞지 않는 값을 대입하거나 비교하는 부분이 있는지 점검하는 것입니다. 이 책에서 다루는 수식 계산기에서는 의미 분석은 하지 않습니다.
파싱(Parsing)에서는 입력 구문의 각 토큰을 번역 결과물로 만들기 위한 과정으로 파서에서 수행합니다. 파서는 다양한 형태로 표현할 수 있는데 정규화를 할 수 있을 때 파서 트리로 구현하면 효과적입니다. 수식 파서 트리는 운행 방법에 따라 원하는 목적물을 만들 수 있습니다.
중간 코드 생성(Midi Code Generation)에서는 파싱한 결과물로 목적 파일을 만드는 과정입니다. 여기에서는 수식 파서 트리를 후위 순회하여 계산 결과를 출력하기로 할게요.
9.3.1 수식 문법 정규화
수식 파서 트리를 만들기 전에 입력 소스에 사용할 수식을 정규화를 하기로 해요. 정규화는 같은 종류의 표현을 묶어 간소화하는 과정입니다. 여기에서는 정규화 표현에 많이 사용하는 BNF로 표현할게요.
BNF 표기법은 Backus Naur Form의 약자로 존 배커스와 나우르가 만든 표기법으로 문법을 수학적인 수식으로 나타낼 때 사용하는 표기법입니다.
단말 표현과 비단말 표현 및 기호를 이용하여 문장 생성 과정을 유도합니다.
단말 표현이란 더 이상 유도할 수 없는 표현으로 수식에서 1, 2, ..., +, -, *, / 등이 있습니다.
비단말 표현이란 유도가 가능한 표현으로 <digit> 처럼 < >를 이용하여 표현합니다.
유도 과정에서 := 는 정의를 의미하며 <digit>:=0|1|2|3|4|5|6|7|8|9 처럼 표현합니다.
만약 순서를 유지해야 하는 표현은 <operator><operand>처럼 순서대로 나열합니다.
생략할 수 있는 선택 표현은 [<sign>]처럼 나타낼 수 있습니다.
그리고 <digit>+처럼 표현하면 <digit>을 최소 한 개 있어야 하고 반복해서 올 수 있음을 의미합니다.
<mid expr>* 처럼 표현하면 <mid expr>이 없거나 반복해서 올 수 있음을 의미합니다.
여기에서는 피연산자로 부호없는 정수가 오고 연산자가 사칙 연산만 가능한 수식을 입력 문장으로 받는 수식 파서 트리를 만들어 봅시다. 이러한 수식을 BNF 표기법으로 표현하면 다음처럼 표현할 수 있습니다.
수식 표현은 맨 먼저 피연산자가 오고 중간 표현이 없거나 반복해서 올 수 있습니다.
<expr>:= <operand><mid expr>*
중간 표현이라 연산자와 피연산자가 순서대로 오는 것을 말합니다.
<mid expr>:=<operator><operand>
연산자는 + 혹은 – 혹은 * 혹은 / 입니다.
<operator>:=+|-|*|/
피연산자는 숫자가 최소 한 개 이상 반복해서 오는 것을 말합니다.
<operand>:=<digit>+
숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 입니다.
<digit>:=0|1|2|3|4|5|6|7|8|9
따라서 다음과 같은 표현은 여기서 만드는 수식 파서 트리에 맞는 표현입니다.
23+4*7-45-6
3*6/2-5*7
29
34-6*9/2
다음과 같은 표현은 여기서 만드는 수식 파서 트리에 맞지 않는 표현입니다.
23+4*745#6
3*6/-25*7
*45
9.3.2 프로토 타이핑
이제 수식 파서 트리(Numeric Parser Tree)를 이용한 계산기를 만들어 보아요. 먼저 프로토 타이핑을 합시다.
계산기는 어휘를 분석하는 어휘 분석기(Lexer)와 구문 분석기(SynAnalyzer)와 수식 파서 트리(Parser)를 이용할 거예요. 그리고 어휘 분석기에서는 토큰(Token)을 생성하는데 토큰의 종류는 연산자(Operator)와 피 연산자(Operand)가 있습니다.
진입점에서는 6가지 테스트 케이스에 사용할 수식 표현을 수식 계산기를 통해 테스트를 합시다.
int main()
{
테스트 케이스에 사용할 수식 표현에는 올바른 수식 표현과 수식에 사용할 수 없는 어휘를 사용한 표현과 구문을 잘못 사용한 표현을 적절하게 정하세요.
char *tc_exprs[6]=
{
"2+3-5*5+6/2"는 올바른 수식이며 후위 표기로 2 3 + 5 5 * - 6 2 / +이며 연산 결과는 -17입니다.
"2+3-5*5+6/2",
"23*5/2+4*6"은 올바른 수식이며 후위 표기로 23 5 * 2 / 4 6 * + 이며 연산 결과는 81입니다.
"23*5/2+4*6",
"2+4*5#6"은 올바른 수식이 아닙니다. 어휘 분석기에서 오류를 찾을 수 있어야겠죠.
"2+4*5#6",
"2+3*5+"는 올바른 수식이 아닙니다. 구문 분석기에서 오류를 찾을 수 있어야겠죠.
"2+3*5+",
"3+36+-7"는 올바른 수식이 아닙니다. 구문 분석기에서 오류를 찾을 수 있어야겠죠.
"3+36+-7",
"45+3*5-2+5/2*7"은 올바른 수식이며 후위 표기로 45 3 5 * + 2 - 5 2 / 7 * + 이며 연산 결과는 72입니다.
"45+3*5-2+5/2*7"
};
테스트 케이스에 사용할 수식 표현을 하나씩 전달하면서 수식 계산기를 테스트 합시다.
for(int i = 0; i<6; i++)
{
수식 계산기는 수식 표현을 입력 인자로 받아 생성합니다.
Calculator *cal = new Calculator(tc_exprs[i]);
그리고 수식 계산기를 수행하게 합시다.
cal->Run();
테스트를 수행한 후에 계산기는 소멸해야겠죠.
delete cal;
}
return 0;
}
수식 계산기를 표현할 Calculator 클래스를 정의합시다.
class Calculator
{
멤버 필드로 입력 수식과 어휘 분석기에 의해 생성한 토큰 컬렉션이 필요하죠. 토큰 컬렉션은 Token *를 템플릿 인자인 벡터를 이용합시다. 나중에 Token 클래스를 정의할 때 Tokens 형식은 정의하기로 해요.
char *expr;
Tokens tokens;
public:
생성자는 입력 인자로 수식 표현을 받습니다.
Calculator(const char *expr);
~Calculator(void);
계산기를 수행하는 메서드를 추가하세요.
void Run();
};
생성자를 정의합시다.
Calculator::Calculator(const char *expr)
{
먼저 입력 인자로 받은 수식의 문자열 길이를 더하세요. 널 문자까지 복사해야 하므로 +1을 합니다.
int len_p1 = strlen(expr)+1;
문자열을 복사할 메모리를 동적으로 할당합니다.
this->expr = new char[len_p1];
문자열을 복사하세요. strcpy_s 함수는 strcpy 함수의 안전한 버전입니다.
strcpy_s(this->expr,len_p1,expr);
}
Calculator::~Calculator(void)
{
소멸자에서는 수식 표현을 저장했던 메모리를 해제하세요.
delete[] expr;
}
void Calculator::Run()
{
계산기를 가동하면 먼저 수식을 출력합시다.
cout<<expr<<"을 계산합니다. ..."<<endl;
Lexer lexer;
먼저 어휘 분석기로 토큰을 생성합니다.
if(lexer.MakeToken(expr))
{
어휘 분석기에서 생성한 토큰 컬렉션을 얻어옵니다.
tokens = lexer.GetTokens();
구문 분석기를 통해 올바른 표현인지 확인합시다. 여기에서 구문 분석기는 올바른 표현인지 확인하는 것 말고는 특별한 작업이나 유지해야 할 상태가 없어서 정적 클래스로 정의하기로 해요.
if(SynAnalyzer::Analyze(tokens))
{
구문 분석을 성공하면 파서를 통해 파싱하세요.
Parser parser(tokens);
parser.Parsing();
파싱 후에 후위 표기로 출력합시다.
parser.PostOrderView();
그리고 계산한 후에 결과를 출력하세요.
cout<<expr<<"="<<parser.Calculate()<<endl;
}
else
{
만약 구문 분석을 실패하면 메시지를 출력합니다.
cout<<"수식에 사용한 표현이 문법에 맞지 않습니다."<<endl;
}
}
else
{
토큰 생성 과정에서 문제가 있을 때도 메시지를 출력하세요.
cout<<"사용할 수 없는 기호가 있습니다."<<endl;
}
cout<<endl;
}
작성한 코드는 모든 구현을 구현 후에 다시 한 번 코드를 보여드릴게요.
9.3.3 토큰 구현
이번에는 수식 파서 트리(Numeric Parser Tree)를 이용한 계산기에서 사용할 토큰을 구현합시다.
먼저 토큰 클래스를 정의합시다.
class Token
{
수식 파서 트리를 만들 때 사용할 우선 순위를 멤버 필드로 선언하세요.
int priority;
public:
토큰 정보를 보여주는 부분은 피연산자와 연산자에 따라 다르므로 순수 가상 메서드(추상 메서드)예요.
virtual void View()const=0;
파서 트리에서 토큰을 매달 때 우선 순위를 비교하는 메서드를 제공합시다.
bool MoreThanPriority(Token *token);
protected:
파생 클래스에서 자신의 우선 순위를 결정할 수 있게 설정자를 추가하세요.
void SetPriority(int priority);
};
여기에서는 토큰을 벡터에 보관할 거예요.
#include <vector>
using namespace std;
Token *형식이 템플릿 인자인 vector를 Tokens 형식으로 지정합시다.
typedef vector<Token *> Tokens;
토큰 컬렉션에 보관한 토큰들을 순회할 수 있는 반복자도 타입 재지정하세요.
typedef Tokens::iterator TIter;
typedef Tokens::const_iterator CTIter;
토큰의 우선 순위를 비교한 결과를 반환하는 메서드를 정의하세요.
bool Token::MoreThanPriority(Token *token)
{
return priority>=token->priority;
}
우선 순위 설정자도 정의하세요.
void Token::SetPriority(int priority)
{
this->priority = priority;
}
이번에는 연산자 토큰을 Operator 이름의 클래스로 정의합시다.
class Operator :
public Token
{
연산 기호를 기억하고 있어야겠죠.
char ch;
public:
생성할 때 연산 기호를 입력 인자로 받습니다.
Operator(char ch);
자신의 정보를 출력하는 View 메서드를 재정의(override) 해야죠.
void View()const;
두 개의 피연산자의 값을 받아 연산하는 메서드를 추가하세요.
int Calculate(int lvalue, int rvalue)const;
정적 메서드로 특정 문자가 연산자가 맞는지 판별하는 메서드를 제공하세요.
static bool IsOperator(char ch);
토큰이 Operator인지 판별하는 메서드를 제공하세요.
static bool IsOperator(const Token *token);
};
생성자를 구현합시다.
Operator::Operator(char ch)
{
입력 인자로 받은 연산 기호를 멤버 필드에 설정하세요.
this->ch = ch;
여기에서는 더하기와 빼기는 우선 순위를 1로 곱하기와 나누기는 2로 설정하기로 해요.
if((ch=='+')||(ch=='-'))
{
SetPriority(1);
}
else
{
SetPriority(2);
}
}
정보를 출력하는 메서드에서는 연산 기호를 출력합니다.
void Operator::View()const
{
cout<<ch<<" ";
}
계산하는 메서드를 구현합시다.
int Operator::Calculate(int lvalue, int rvalue)const
{
연산 기호에 따라 알맞은 연산을 수행한 결과를 반환하세요.
switch(ch)
{
case '+': return lvalue + rvalue;
case '-': return lvalue - rvalue;
case '*': return lvalue * rvalue;
case '/':
나누기 연산에서는 오른쪽 피연산자 값이 0이 아닐 때만 나눈 값을 반환하세요.
if(rvalue)
{
return lvalue / rvalue;
}
오픈쪽 피연산자가 0이면 나누기 제로 오류가 있음을 출력하세요.
cout<<"divide zero error"<<endl;
return 0;
}
만약 다른 연산 기호라면 프로그램에 버그가 있는 것입니다.
throw "연산자 기호에 문제가 있습니다.";
}
문자가 사칙 연산 기호인지 판별하는 메서드를 구현하세요.
bool Operator::IsOperator(char ch)
{
여기에서는 사칙 연산만 연산자로 제공할 거예요.
return (ch=='+')||(ch=='-')||(ch=='*')||(ch=='/');
}
토큰이 연산자인지 판별하는 메서드를 구현하세요.
bool Operator::IsOperator(const Token *token)
{
dynamic_cast 결과가 0이 아니면 연산자입니다.
return dynamic_cast<const Operator *>(token)!=0;
}
피연산자 토큰은 Operand 이름의 클래스로 정의합시다.
class Operand:
public Token
{
피연산자 값을 멤버 필드로 선언하세요.
int value;
public:
생성자에서는 피연산자의 값을 입력 인자로 받습니다.
Operand(int value);
자신의 정보를 출력하는 View 메서드를 재정의해 주어야 합니다.
void View()const;
피연산자 값의 접근자 메서드를 제공하세요.
int GetValue()const;
문자가 숫자 문자인지 판별하는 정적 메서드를 제공하세요.
static bool IsDigit(char ch);
문자열을 정수로 변환하는 정적 메서드를 제공하세요. 변환후 에 다음 토큰의 위치를 판단하기 위해 인덱스를 참조 형식으로 받습니다.
static int ConvertStrToInt(const char *str,int &index);
토큰이 피연산자인지 판별하는 정적 메서드를 제공하세요.
static bool IsOperand(const Token *token);
};
생성자를 정의합시다.
Operand::Operand(int value)
{
입력 인자로 전달받은 피연산자 값을 멤버 필드 value에 설정하세요.
this->value = value;
우선 순위는 제일 높은 3으로 설정하세요.
SetPriority(3);
}
자신의 정보를 출력하는 메서드를 구현하세요.
void Operand::View()const
{
cout<<value<<" ";
}
피연산자 값의 접근자 메서드를 구현하세요.
int Operand::GetValue()const
{
return value;
}
문자가 정수 문자인지 판별하는 메서드를 구현하세요.
bool Operand::IsDigit(char ch)
{
정수 문자는 '0'보다 값이 크거나 같고 '9'보다 작거나 같습니다.
return (ch>='0')&&(ch<='9');
}
문자열을 정수로 변환하는 메서드를 구현하세요.
int Operand::ConvertStrToInt(const char *str,int &index)
{
초기 값을 0으로 설정합니다.
int value = 0;
정수 문자가 아닌 문자가 나올 때까지 반복합니다.
while(IsDigit(str[index]))
{
현재 값에 10을 곱한 후에 문자 - '0'을 하세요. str[i]가 '8'일 때 str[i] - '0'은 8입니다.
value = value * 10 + str[index] - '0';
인덱스를 1 증가하세요.
index++;
}
변환한 값을 반환하세요.
return value;
}
토큰이 피연산자인지 판별하는 메서드를 구현하세요.
bool Operand::IsOperand(const Token *token)
{
dynamic_cast 결과가 0이 아니면 연산자입니다.
return dynamic_cast<const Operand *>(token)!=0;
}
여기에서는 정수 문자인지 판별하거나 문자열을 정수로 변환하는 메서드를 직접 구현하였습니다. 물론 라이브러리 함수를 사용할 수도 있겠죠.
9.3.4 어휘 분석기(Lexer)와 구문 분석기(SynAnalyzer) 구현
이번에는 수식 파서 트리를 이용한 계산기의 어휘 분석기와 구문 분석기를 구현해 보아요.
먼저 어휘분석기를 구현합시다.
class Lexer
{
어휘분석기에서는 수식을 입력받아 토큰을 생성합니다. 토큰을 보관하는 컬렉션을 멤버 필드로 선언하세요.
Tokens tokens;
public:
수식을 입력받아 토큰을 생성하는 메서드를 추가하세요. 토큰 생성 과정에서 수식에 오류가 없는지 여부를 반환하세요.
bool MakeToken(const char *expr);
생성한 토큰을 보관한 컬렉션을 제공하는 메서드를 추가하세요.
Tokens GetTokens()const;
동적으로 생성한 토큰들을 소멸하기 위해 소멸자가 필요합니다.
~Lexer();
};
수식을 입력받아 토큰을 생성하는 메서드를 구현합시다.
bool Lexer::MakeToken(const char *expr)
{
이전에 생성했던 토큰들을 지우세요.
tokens.clear();
int i = 0;
수식 문자열이 종료 문자('\0', 널문자)를 만날 때까지 반복합니다.
while(expr[i])
{
만약 현재 문자가 연산자에 사용하는 문자인지 판별합니다.
if(Operator::IsOperator(expr[i]))
{
연산자에 사용하는 문자면 연산자 토큰을 생성하여 컬렉션에 추가하세요.
tokens.push_back(new Operator(expr[i]));
연산자는 단일 문자가 토큰이므로 다음 토큰 위치는 i를 1 증가한 위치입니다.
i++;
}
else
{
만약 현재 문자가 연산자에 사용하는 문자가 아니면 숫자 문자인지 판별합니다.
if(Operand::IsDigit(expr[i]))
{
숫자 문자일 때는 해당 위치에서의 문자열을 정수로 변환후에 피연산자 토큰 생성 및 컬렉션에 추가하세요.
int value = Operand::ConvertStrToInt(expr,i);
tokens.push_back(new Operand(value));
}
else
{
연산자에 사용하는 문자도 숫자 문자도 아니면 잘못 사용한 어휘가 있는 것이므로 거짓을 반환하세요.
return false;
}
}
}
종료 문자까지 분석하였다면 잘못 사용한 어휘가 없는 것이므로 참을 반환하세요.
return true;
}
토큰 컬렉션을 제공하는 메서드를 구현하세요.
Tokens Lexer::GetTokens()const
{
return tokens;
}
소멸자를 구현합시다.
Lexer::~Lexer()
{
컬렉션의 모든 요소를 반복자를 이용하여 방문하세요.
TIter seek = tokens.begin();
TIter last = tokens.end();
for( ;seek != last; ++seek)
{
반복자가 가리키는 위치의 토큰을 소멸하세요.
delete (*seek);
}
}
구문 분석기를 구현합시다.
class SynAnalyzer
{
public:
구문 분석기에서는 생성한 토큰들이 적절한 순서인지 판별하는 기능만 필요하여 정적 메서드로 추가하세요.
static bool Analyze(Tokens tokens);
};
bool SynAnalyzer::Analyze(Tokens tokens)
{
먼저 컬렉션에 보관한 토큰 개수를 구하세요.
int tcnt = tokens.size();
여기에서 계산할 수 있는 수식은 언제나 토큰 개수가 홀수여야 합니다.
if(tcnt%2==0)
{
return false;
}
첫 번째 토큰은 언제나 피연산자여야 합니다.
<expr>:= <operand><mid expr>*
if(Operand::IsOperand(tokens[0])==false)
{
return false;
}
그리고 피연산자와 연산자로 구성한 중간 표현이 반복해서 올 수 있습니다.
<expr>:= <operand><mid expr>*
for(int i = 1; i<tcnt; i+=2)
{
중간 표현은 연산자와 피연산자 순으로 와야 합니다.
<mid expr>:=<operator><operand>
if(Operator::IsOperator(tokens[i])==false)
{
return false;
}
if(Operand::IsOperand(tokens[i+1])==false)
{
return false;
}
}
중간에 오류가 없다면 참을 반환하세요.
return true;
}
9.3.5 수식 파서 트리 구현
이번에는 수식 파서 트리를 구현하기로 해요.
class Parser
{
수식 파서 트리에서는 어휘 분석기에서 생성한 토큰 컬렉션에 있는 토큰들을 파서 트리에 매달 것입니다. 이에 토큰 컬렉션을 멤버 필드로 선언하세요.
Tokens tokens;
struct Node
{
노드에는 토큰을 자료로 갖습니다.
Token *token;
Node *lc;
Node *rc;
Node(Token *token)
{
this->token = token;
lc = rc = 0;
}
};
루트를 기억할 멤버가 필요하겠죠.
Node *root;
public:
생성자에서는 토큰 컬렉션을 입력 인자로 받습니다.
Parser(Tokens tokens);
~Parser(void);
파서 트리에 파싱하는 메서드를 제공합시다.
void Parsing();
후위 표기로 출력하는 메서드도 제공합시다.
void PostOrderView()const;
계산하는 메서드를 제공합시다.
int Calculate();
private:
내부적으로 토큰을 파서 트리에 매다는 메서드가 필요합니다.
void Add(Token *token);
후위 표기로 출력하기 위해 후위 순회하는 메서드가 필요합니다.
void PostOrder(Node *sr)const;
계산할 때도 후위 순회하며 계산합니다.
int PostOrderCalculate(Node *sr);
소멸할 때 동적으로 생성한 모든 노드를 소멸해야겠죠.
void Clear(Node *sr);
};
생성자에서는 입력 인자로 받은 컬렉션을 멤버 필드에 설정하세요.
Parser::Parser(Tokens tokens)
{
this->tokens = tokens;
}
소멸자에서는 Clear 메서드를 호출하여 모든 노드를 소멸합니다.
Parser::~Parser(void)
{
Clear(root);
}
void Parser::Clear(Node *sr)
{
모든 노드를 소멸할 때 후위 순회로 소멸해야 합니다.
if(sr)
{
Clear(sr->lc);
Clear(sr->rc);
delete sr;
}
}
파싱하는 메서드를 구현합시다.
void Parser::Parsing()
{
먼저 토큰 개수를 구하세요.
int tcnt = tokens.size();
첫 번째 토큰으로 노드를 생성하여 root에 설정하세요.
root = new Node(tokens[0]);
for(int i = 1; i<tcnt;i++)
{
반복해서 모든 토큰을 파서 트리에 추가하세요.
Add(tokens[i]);
}
}
토큰을 파서 트리에 매다는 메서드를 구현합시다.
void Parser::Add(Token *token)
{
먼저 입력 인자로 받은 토큰을 입력 인자로 노드를 생성하세요.
Node *now = new Node(token);
루트의 토큰을 구하세요.
Token *st = root->token;
루트의 토큰의 우선 순위가 추가할 토큰의 우선 순위보다 크거나 같은지 판별하세요.
if(st->MoreThanPriority(token))
{
예를 들어 추가할 노드의 기호가 더하기나 빼기 기호일 때는 현재 루트에 있는 토큰들은 새로운 노드의 왼쪽 피연산자로 들어가야 합니다. 그리고 루트는 now로 변경해야겠죠.
now->lc = root;
root = now;
다음은 root의 토큰 우선 순위가 추가할 토큰의 우선 순위보다 크거나 같을 때 링크를 조절하는 과정을 논리적으로 도식한 것입니다.
}
else
{
root의 토큰 우선 순위가 추가할 토큰의 우선 순위보다 작을 때는 새로 추가하는 노드가 피연산자일 때와 연산자일 때 코드가 조금 다릅니다.
if(Operand::IsOperand(token)==false)
{
연산자일 때는 새로운 노드의 왼쪽 자식으로 루트의 오른쪽 자식을 매달고 루트의 오른쪽 자식에 새로운 노드를 매답니다.
now->lc = root->rc;
root->rc = now;
다음은 root의 토큰 우선 순위가 추가할 토큰의 우선 순위보다 작으면서 연산자일 때 링크를 조절하는 과정을 논리적으로 도식한 것입니다.
}
else
{
새로 추가할 토큰이 피연산일 때는 루트에서 오른쪽 자식이 없는 노드를 찾아서 매답니다.
Node *pa = root;
while(pa->rc)
{
pa = pa->rc;
}
pa->rc = now;
다음은 root의 토큰 우선 순위가 추가할 토큰의 우선 순위보다 작으면서 피연산자일 때 링크를 조절하는 과정을 논리적으로 도식한 것입니다.
}
}
}
후위 순위로 출력하는 메서드를 구현하세요.
void Parser::PostOrderView()const
{
PostOrder(root);
cout<<endl;
}
void Parser::PostOrder(Node *sr)const
{
if(sr)
{
PostOrder(sr->lc);
PostOrder(sr->rc);
sr->token->View();
}
}
계산하여 결과를 반환하는 메서드를 구현하세요.
int Parser::Calculate()
{
return PostOrderCalculate(root);
}
int Parser::PostOrderCalculate(Node *sr)
{
if(sr->lc)
{
여기에서 구현할 수식 파서 트리에서 모든 노드는 자식이 둘이거나 없습니다. 연산자는 자식이 둘 있고 피연산자는 자식이 없습니다. 따라서 왼쪽 자식이 있다는 것은 연산자를 의미합니다. 먼저 왼쪽 서브 트리를 계산하세요. 그리고 오른쪽 서브 트리를 계산합시다.
int lvalue = PostOrderCalculate(sr->lc);
int rvalue = PostOrderCalculate(sr->rc);
현재 토큰을 연산자 토큰으로 변환하세요.
Operator *op = dynamic_cast<Operator *>(sr->token);
그리고 연산 후에 결과를 반환하세요.
return op->Calculate(lvalue, rvalue);
}
else
{
피연산자일 때는 값을 반환합니다.
Operand *op = dynamic_cast<Operand *>(sr->token);
return op->GetValue();
}
}
9.3.6 수식 파서 트리를 이용한 계산기 코드
앞에서 구현한 수식 파서 트리를 이용한 계산기의 실행 결과입니다.
▷ 실행 결과
2+3-5*5+6/2을 계산합니다. ...
2 3 + 5 5 * - 6 2 / +
2+3-5*5+6/2=-17
23*5/2+4*6을 계산합니다. ...
23 5 * 2 / 4 6 * +
23*5/2+4*6=81
2+4*5#6을 계산합니다. ...
사용할 수 없는 기호가 있습니다.
2+3*5+을 계산합니다. ...
수식에 사용한 표현이 문법에 맞지 않습니다.
3+36+-7을 계산합니다. ...
수식에 사용한 표현이 문법에 맞지 않습니다.
45+3*5-2+5/2*7을 계산합니다. ...
45 3 5 * + 2 - 5 2 / 7 * +
45+3*5-2+5/2*7=72
다음은 전체 코드입니다.
//Token.h
#pragma once
#include <iostream>
using namespace std;
#include <string.h>
class Token
{
int priority;
public:
virtual void View()const=0;
bool MoreThanPriority(Token *token);
protected:
void SetPriority(int priority);
};
#include <vector>
using namespace std;
typedef vector<Token *> Tokens;
typedef Tokens::iterator TIter;
typedef Tokens::const_iterator CTIter;
//Token.cpp
#include "Token.h"
bool Token::MoreThanPriority(Token *token)
{
return priority>=token->priority;
}
void Token::SetPriority(int priority)
{
this->priority = priority;
}
//Operator.h
#pragma once
#include "token.h"
class Operator :
public Token
{
char ch;
public:
Operator(char ch);
void View()const;
int Calculate(int lvalue, int rvalue)const;
static bool IsOperator(char ch);
static bool IsOperator(const Token *token);
};
//Operator.cpp
#include "Operator.h"
Operator::Operator(char ch)
{
this->ch = ch;
if((ch=='+')||(ch=='-'))
{
SetPriority(1);
}
else
{
SetPriority(2);
}
}
void Operator::View()const
{
cout<<ch<<" ";
}
int Operator::Calculate(int lvalue, int rvalue)const
{
switch(ch)
{
case '+': return lvalue + rvalue;
case '-': return lvalue - rvalue;
case '*': return lvalue * rvalue;
case '/':
if(rvalue)
{
return lvalue / rvalue;
}
cout<<"divide zero error"<<endl;
return 0;
}
throw "연산자 기호에 문제가 있습니다.";
}
bool Operator::IsOperator(char ch)
{
return (ch=='+')||(ch=='-')||(ch=='*')||(ch=='/');
}
bool Operator::IsOperator(const Token *token)
{
return dynamic_cast<const Operator *>(token)!=0;
}
//Operand.h
#pragma once
#include "Token.h"
class Operand:
public Token
{
int value;
public:
Operand(int value);
void View()const;
int GetValue()const;
static bool IsDigit(char ch);
static int ConvertStrToInt(const char *str,int &index);
static bool IsOperand(const Token *token);
};
//Operand.cpp
#include "Operand.h"
Operand::Operand(int value)
{
this->value = value;
SetPriority(3);
}
void Operand::View()const
{
cout<<value<<" ";
}
int Operand::GetValue()const
{
return value;
}
bool Operand::IsDigit(char ch)
{
return (ch>='0')&&(ch<='9');
}
int Operand::ConvertStrToInt(const char *str,int &index)
{
int value = 0;
while(IsDigit(str[index]))
{
value = value * 10 + str[index] - '0';
index++;
}
return value;
}
bool Operand::IsOperand(const Token *token)
{
return dynamic_cast<const Operand *>(token)!=0;
}
//Lexer.h
#pragma once
#include "Operand.h"
#include "Operator.h"
class Lexer
{
Tokens tokens;
public:
bool MakeToken(const char *expr);
Tokens GetTokens()const;
~Lexer();
};
//Lexer.cpp
#include "Lexer.h"
bool Lexer::MakeToken(const char *expr)
{
tokens.clear();
int i = 0;
while(expr[i])
{
if(Operator::IsOperator(expr[i]))
{
tokens.push_back(new Operator(expr[i]));
i++;
}
else
{
if(Operand::IsDigit(expr[i]))
{
int value = Operand::ConvertStrToInt(expr,i);
tokens.push_back(new Operand(value));
}
else
{
return false;
}
}
}
return true;
}
Tokens Lexer::GetTokens()const
{
return tokens;
}
Lexer::~Lexer()
{
TIter seek = tokens.begin();
TIter last = tokens.end();
for( ;seek != last; ++seek)
{
delete (*seek);
}
}
//SynAnalyzer.h
#pragma once
#include "Operator.h"
#include "Operand.h"
class SynAnalyzer
{
public:
static bool Analyze(Tokens tokens);
};
//Parser.h
#pragma once
#include "Operator.h"
#include "Operand.h"
class Parser
{
Tokens tokens;
struct Node
{
Token *token;
Node *lc;
Node *rc;
Node(Token *token)
{
this->token = token;
lc = rc = 0;
}
};
Node *root;
public:
Parser(Tokens tokens);
~Parser(void);
void Parsing();
void PostOrderView()const;
int Calculate();
private:
void Add(Token *token);
void PostOrder(Node *sr)const;
int PostOrderCalculate(Node *sr);
void Clear(Node *sr);
};
//Parser.cpp
#include "Parser.h"
Parser::Parser(Tokens tokens)
{
this->tokens = tokens;
}
Parser::~Parser(void)
{
Clear(root);
}
void Parser::Clear(Node *sr)
{
if(sr)
{
Clear(sr->lc);
Clear(sr->rc);
delete sr;
}
}
void Parser::Parsing()
{
int tcnt = tokens.size();
root = new Node(tokens[0]);
for(int i = 1; i<tcnt;i++)
{
Add(tokens[i]);
}
}
void Parser::Add(Token *token)
{
Node *now = new Node(token);
Token *st = root->token;
if(st->MoreThanPriority(token))
{
now->lc = root;
root = now;
}
else
{
if(Operand::IsOperand(token)==false)
{
now->lc = root->rc;
root->rc = now;
}
else
{
Node *pa = root;
while(pa->rc)
{
pa = pa->rc;
}
pa->rc = now;
}
}
}
void Parser::PostOrderView()const
{
PostOrder(root);
cout<<endl;
}
void Parser::PostOrder(Node *sr)const
{
if(sr)
{
PostOrder(sr->lc);
PostOrder(sr->rc);
sr->token->View();
}
}
int Parser::Calculate()
{
return PostOrderCalculate(root);
}
int Parser::PostOrderCalculate(Node *sr)
{
if(sr->lc)
{
int lvalue = PostOrderCalculate(sr->lc);
int rvalue = PostOrderCalculate(sr->rc);
Operator *op = dynamic_cast<Operator *>(sr->token);
return op->Calculate(lvalue, rvalue);
}
else
{
Operand *op = dynamic_cast<Operand *>(sr->token);
return op->GetValue();
}
}
//Calculator.h
#pragma once
#include "Lexer.h"
#include "SynAnalyzer.h"
#include "Parser.h"
class Calculator
{
char *expr;
Tokens tokens;
public:
Calculator(const char *expr);
~Calculator(void);
void Run();
};
//Calculator.cpp
#include "Calculator.h"
Calculator::Calculator(const char *expr)
{
int len_p1 = strlen(expr)+1;
this->expr = new char[len_p1];
strcpy_s(this->expr,len_p1,expr);
}
Calculator::~Calculator(void)
{
delete[] expr;
}
void Calculator::Run()
{
cout<<expr<<"을 계산합니다. ..."<<endl;
Lexer lexer;
if(lexer.MakeToken(expr))
{
tokens = lexer.GetTokens();
if(SynAnalyzer::Analyze(tokens))
{
Parser parser(tokens);
parser.Parsing();
parser.PostOrderView();
cout<<expr<<"="<<parser.Calculate()<<endl;
}
else
{
cout<<"수식에 사용한 표현이 문법에 맞지 않습니다."<<endl;
}
}
else
{
cout<<"사용할 수 없는 기호가 있습니다."<<endl;
}
cout<<endl;
}
//Program.cpp
#include "Calculator.h"
int main()
{
char *tc_exprs[6]=
{
"2+3-5*5+6/2", "23*5/2+4*6", "2+4*5#6",
"2+3*5+", "3+36+-7", "45+3*5-2+5/2*7"
};
for(int i = 0; i<6; i++)
{
Calculator *cal = new Calculator(tc_exprs[i]);
cal->Run();
delete cal;
}
return 0;
}
'언어 자료구조 알고리즘 > [C++]디딤돌 자료구조와 알고리즘' 카테고리의 다른 글
| 10.2.1 순열 문제 구현 (0) | 2016.04.11 |
|---|---|
| 10. 2 순열 문제 [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.11 |
| 10.1 피보나치 수열 [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.11 |
| 10. 동적 프로그래밍(DYNAMIC PROGRAMMING) [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.11 |
| 9.4 병합 정렬(Merge Sort) [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |
| 9.2 스택을 이용한 수식 파서 [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |
| 9.1 힙 정렬 알고리즘 [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |
| 9. 기타 이진 트리 및 분할 정복 [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |
| 8.7 장르별 도서 관리 프로그램 코드[디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |
| 8.6 도서 삭제 및 소멸 [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |