BNF
BNF(배커스 나우르 표기법, Backus-Naur Form)는 문맥 자유 문법(Context-Free Grammar)을 기술하기 위해 존 배커스와 페테르 나우르가 만든 표기법입니다. BNF는 단말 기호(terminal symbol)와 비단말 기호(nonterminal symbol)를 이용해서 문맥 자유 문법을 기술합니다.
- 단말 기호
- 다른 기호에서 유도되지 않는 기호입니다.
(나+같이 있는 그대로 사용되는 기호라고 하면 되겠습니다. 비단말 기호 - 다른 기호를 조합하여 유도되는 기호입니다.
비단말 기호가 어떻게 유도되는지는 명확하게 정의해주어야 합니다. 정의는 ::=를 써서 나타냅니다.
<zero> ::= "0"
<zero>라는 비단말 기호를 "0"으로 정의했습니다. 비단말 기호는 기호를 여러 개 나열하여 정의할 수도 있습니다.
<one> ::= "1"
<ten> ::= <one> <zero>
먼저 <one>을 정의한다음, <ten>을 <one>과 <zero>를 순서대로 늘어놓은 것으로 정의했습니다. 당연하겠지만 순서가 바뀌면 안 됩니다. 또한 비단말 기호가 여러 정의 중 하나를 선택하게 할 수도 있습니다.
<digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<digit>를 "0"부터 "9" 중 하나로 정의했습니다. 이 때 | 기호는 이 정의들 중 하나를 선택하라는 의미입니다.
짝이 맞는 괄호 문자열
짝이 맞는 괄호 문자열 <S>는 다음과 같이 정의 가능합니다.
<S> ::= "()" | "(" <S> ")" | <S> <S>
즉, <S>는 안이 빈 괄호 문자열 "()"이거나 여는 괄호와 닫는 괄호로 둘러싸인 짝이 맞는 괄호 문자열이거나 짝이 맞는 괄호 문자열 두 개를 이어 붙인 것입니다. 이 문법에서 문자열 "(()())()"는 아래 그림처럼 해석됩니다.
양의 십진수
<digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<decimal> ::= <digit> | <digit> <decimal>
먼저 위에서 봤던 것과 동일하게 <digit>를 정의하고 <decimal>은 <digit>이거나 <digit> 뒤에 <decimal>이 붙은 것으로 정의합니다. 물론 이 문법은 "00018351"같은 것도 십진수로 허용해주지만, 그 정도는 너그럽게 봐줍시다.
표현식
표현식(expression)이란 변수, 함수, 연산자 등이 조합되어 컴퓨터로 값을 계산하여 도출해낼 수 있는 것을 말합니다. 이때 계산 과정은 평가(evaluation)이라고 하죠. 표현식의 예로는 2+3, max(5,7)+a*c, a+1<b가 있습니다. 반면에 if문, for문 등은 의미는 있지만 이들이 값을 가지는 것이 아니므로 표현식이 아닌 구문(statement)이라고 부릅니다.
십진수 상수와 "+", "-", "*", 괄호만 허용하는 아주 간단한 표현식 문법을 생각합시다. 이때 표현식은 덧셈 또는 뺄셈으로 연결된 항(term)들의 나열로 나타낼 수 있습니다. BNF로는
<expr> ::= <term> | <term> "+" <expr> | <term> "-" <expr>
항은 인수(factor)들의 곱으로 나타낼 수 있습니다.
<term> ::= <factor> | <factor> "*" <term>
여기서부터 복잡합니다. 인수로 가능한 것들은 (3+5*7), -65, +(4-1)이 있습니다. 먼저 앞에 부호를 나타내는 "+"와 "-"부터 떼줍니다. 이걸 primary expression이라고 하겠습니다.
<factor> ::= <primary-expr> | "+" <factor> | "-" <factor>
primary expression은 십진수 상수이거나 표현식을 괄호로 감싼 것입니다.
<primary-expr> ::= <decimal> | "(" <expr> ")"
예시로 표현식 -(1+2*3)*(4-6)은 다음 그림처럼 해석됩니다.
매우 길지만 이렇듯 명확하게 모든 문법 요소를 트리 구조로 나타낼 수 있다는 게 BNF의 장점입니다.
낱말 분석
낱말 분석(Lexical Analysis)은 주어진 문장을 토큰(token)으로 쪼개는 과정입니다. 여기서 토큰은 낱말처럼 의미를 가지는 최소 단위를 말합니다. 토큰에는 식별자(identifier, 변수나 함수 등의 이름), 키워드, 리터럴(상수), 구분자(separator, 세미콜론이나 괄호같은 것), 연산자, 주석이 있습니다. 그리고 이렇게 낱말 분석을 해주는 프로그램을 렉서(lexer) 또는 토크나이저(tokenizer)라고 합니다.
짝이 맞는 괄호 문자열 "(()())()"은 아래와 같이 쪼갤 수 있습니다. "()"를 한 토큰으로 처리한 것에 유의합시다.
"(", "()", "()", ")", "()"
이를 처리하는 코드는 다음과 같습니다. 잘못된 문자열이 들어온 경우는 딱히 처리하지 않았습니다.
using namespace std;
enum class TokenType {
PAR_OPEN,
PAR_CLOSE,
PAR_PAIR,
};
vector<TokenType> tokenize(string s) {
vector<TokenType> res;
for (int i = 0; i < (int)s.size(); i++) {
if (s[i] == ')')
res.push_back(TokenType::PAR_CLOSE);
else if (i != (int)s.size()-1 && s[i+1] == ')') {
res.push_back(TokenType::PAR_PAIR);
i++;
}
else
res.push_back(TokenType::PAR_OPEN);
}
return res;
}
int main(void) {
string s = "(()())()";
vector<TokenType> tokens = tokenize(s);
for (TokenType token : tokens) {
if (token == TokenType::PAR_OPEN)
cout << "PAR_OPEN ";
else if (token == TokenType::PAR_CLOSE)
cout << "PAR_CLOSE ";
else
cout << "PAR_PAIR ";
}
return 0;
}
한편 표현식 -123*(76+5)는
"-", 123, "*", "(", 76, "+", 5, ")"
로 쪼개집니다. 이에 대한 코드는
using namespace std;
enum class TokenType {
INTEGER, // 정수 리터럴
OPSEP, // 연산자와 구분자 (= 정수 리터럴이 아닌 것)
PLUS, // +
MINUS, // -
ASTERISK, // *
PAR_OPEN, // (
PAR_CLOSE, // )
};
struct Token {
TokenType type;
string value;
Token(TokenType t, string v="") : type(t), value(v) {}
};
vector<Token> tokenize(string &s) {
// s에 개행 문자 하나를 추가해줍니다.
// 문장 마지막이 정수 리터럴로 끝나는 경우를 처리하기 쉬워집니다.
s.push_back('\n');
vector<Token> res;
string::iterator cur_token_begin;
TokenType cur_token_type = TokenType::OPSEP;
for (auto it = s.begin(); it != s.end(); it++) {
// 현재 처리하는 토큰의 종류(정수 리터럴인지 아닌지)에 따라 경우가 나뉩니다.
switch (cur_token_type) {
// 정수 리터럴이 아닌 경우
case TokenType::OPSEP:
switch (*it) {
// 공백은 건너뜁니다.
case '\t': case '\n': case '\v': case '\f': case '\r': case ' ':
break;
// 숫자를 만나면 여기가 정수 리터럴의 시작입니다.
// cur_token_type을 INTEGER로 바꾸고
// 정수 리터럴의 시작 위치를 cur_token_begin에 넣어줍니다.
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
cur_token_type = TokenType::INTEGER;
cur_token_begin = it;
break;
// 나머지는 연산자와 구분자입니다. 글자 하나가 바로 토큰 하나입니다.
case '+':
res.push_back(Token(TokenType::PLUS)); break;
case '-':
res.push_back(Token(TokenType::MINUS)); break;
case '*':
res.push_back(Token(TokenType::ASTERISK)); break;
case '(':
res.push_back(Token(TokenType::PAR_OPEN)); break;
case ')':
res.push_back(Token(TokenType::PAR_CLOSE)); break;
default:;
}
break;
// 현재 처리하는 토큰이 정수 리터럴인 경우
default:
// 현재 글자가 숫자가 아니라면 정수 리티럴의 끝입니다.
// 정수 리터럴에 해당하는 문자열을 만들어서 토큰 목록에 넣고
// cur_token_type을 OPSEP으로 만들어줍니다.
// 그리고 현재 글자를 다시 정수 리터럴이 아닌 것으로 처리하도록
// 이전 글자로 한 번 되돌아갑니다. (for문에서 it가 증가하므로)
if (!isdigit(*it)) {
res.push_back(Token(TokenType::INTEGER, string(cur_token_begin, it)));
cur_token_type = TokenType::OPSEP;
it--;
}
// 현재 글자가 숫자라면, 아무 문제 없습니다. 다음 글자로 진행합니다.
}
}
return res;
}
역시 잘못된 입력은 따로 처리하지 않으며, 입력에 공백을 허용하였습니다. 물론 공백은 아무런 의미가 없습니다.
사실 어디까지를 의미를 가지는 최소 단위로 볼 것이냐에 따라 토큰으로 쪼개는 방법은 달라질 수 있으니 위 방법들도 하나의 예시라고 할 수 있겠습니다.
재귀 하향 파서
파싱(parsing, 또는 구문 분석)은 토큰들의 위계 관계를 분석하는 과정입니다. 즉, 각 토큰이 문법적으로 어떤 요소에 해당하는지 알아내는 것이죠. C에서 따지자면 이 "+"가 덧셈을 의미하는지 부호를 나타내는 단항 연산자인지, 또는 "("가 식의 계산 순서를 나타내기 위한 것인지 함수 호출에 사용되는 괄호인지를 알아내는 과정입니다. 파싱을 거치고 나면 저 위에 그린 BNF 트리 그림과 똑같은 게 나옵니다. 이 트리가 구해지면 식 평가는 쉽습니다. 자식 서브트리들을 먼저 평가하고, 이 루트 노드의 토큰에 따라 적절히 자식 서브트리의 값을 조합해주면 트리가 평가됩니다. 파싱을 해주는 프로그램이 바로 파서(parser)입니다.
파서는 크게 하향식과 상향식으로 나뉩니다. 하향식은 전체 토큰들을 받고서 이를 잘게 쪼개고 쪼갠 것들을 다시 처리하는 분할 정복같은 방식으로 작동하고, 상향식은 각 토큰을 하나씩 합치면서 전체 토큰에 해당하는 트리를 만들어냅니다. 여기서는 (아마도) 제일 간단한 재귀 하향 파서(recursive descent parser)를 쓰겠습니다. 이 방식은 모든 비단말 기호에 대응하는 파싱 함수를 만들고, 이 함수가 BNF에 정의된 대로 비단말 기호를 유도하는 다른 기호에 대응되는 함수를 재귀적으로 호출합니다. 예를 들어 다음과 같은 문법을 생각합시다.
<spam> ::= <egg> <bacon> | <baked-beans> <spam>
먼저 <egg>, <bacon>, <baked-beans>에 대응하는 파싱 함수를 만듭니다. 그리고 <spam>에 대응하는 파싱 함수를 만들어야 하는데, 이 함수는 제일 처음 주어진 문자열을 <egg>에 해당하는 함수로 파싱해봅니다. 성공하면, 이미 파싱된 부분은 빼고 나머지를 <bacon>에 해당하는 함수로 파싱합니다. 여기까지 성공하면 파싱 끝이고, <bacon>으로 파싱이 안 되거나 처음부터 <egg>로 파싱이 안 되면 주어진 문자열은 <baked-beans> <spam> 문법에 대응하는 거죠. 따라서 <baked-beans>로 파싱한 다음 나머지 부분을 <spam> 재귀 호출로 처리합니다. 둘 중 하나라도 실패하면 이 문자열은 <spam>이 아닌 겁니다.
좌측 재귀와 EBNF
BNF는 문법적 구조만 설명해주지, 이 구조가 어떻게 평가될지는 설명하지 않습니다. 분명히 "+", "-", "*", 괄호와 정수 리터럴만 쓰는 모든 표현식은 위에서 소개한 BNF로 파싱할 수 있지만 우리가 생각하는 연산자 우선순위와 안 맞습니다. 가령 4-5-10라는 표현식은 우리가 아는 대로라면 (4-5)-10 형태로 평가되어야 하지만, 위 BNF는 먼저 4를 <term>으로 파싱하고, "-"를 파싱하고, 마지막으로 5-10을 <expr> 재귀 호출로 처리하므로 평가 순서는 사실 4-(5-10)입니다.
이걸 해결하려면 BNF를 조금 손봐야 합니다. <expr>을 이렇게 정의하면 어떨까요?
<expr> ::= <term> | <expr> "+" <term> | <expr> "-" <term>
이 문법에서는 주어진 문자열을 <expr>로 파싱할 때 먼저 <term>인지 확인해봅니다. <term>으로 파싱하고 남는 게 없으면 성공이고, 아니면 다시 <expr>을 호출합니다. 이 <expr>은 다시 <expr>을 부르고, 또 <expr>을 부르고… 결국 무한 재귀의 늪에 빠져버립니다.
이 문제는 좌측 재귀(left recursion)이라고 부르는데, BNF를 수정해서 좌측 재귀를 제거하는 여러 방법이 있지만 연산자 우선순위까지 고려하면 이게 꽤 복잡해집니다. 이 글에서는 BNF를 확장한 EBNF(Extended BNF)를 사용해 해결해보겠습니다. EBNF는 BNF에 몇 가지 기호를 추가하였습니다.
*: 앞 기호가 0번 이상 반복됨+: 앞 기호가 1번 이상 반복됨?: 앞 기호가 없거나 하나 있음(): 그룹화
예를 들어
<c> ::= <a> <b>*
는
<c> ::= <a> | <a> <b> | <a> <b> <b> | ...
와 똑같습니다.
<c> ::= <a> (<b> <a>)+
는 괄호 안 전체가 1번 이상 반복되므로
<c> ::= <a> <b> <a> | <a> <b> <a> <b> <a> | <a> <b> <a> <b> <a> <b> <a> | ...
와 같습니다.
<c> ::= <a> (<a> | <b>)?
는 괄호가 <a> 또는 <b>의 값을 가질 수 있고 이것이 없거나 있으므로
<c> ::= <a> | <a> <a> | <a> <b>
와 같습니다.
EBNF는 표시할 수 있는 문법의 범주가 BNF와 완전히 똑같습니다만, 반복을 쓸 수 있게 되어서 재귀 하향 파서를 만들 때 무한 재귀를 피할 수 있게 해줍니다. 예를 들어 위 표현식의 문법을 EBNF로 다시 쓰면 다음과 같이 좌측 재귀를 없앨 수 있습니다.
<expr> ::= <term> (("+" | "-") <term>)*
<term> ::= <factor> ("*" <factor>)*
<factor> ::= <primary-expr> | ("+" | "-") <factor>
<primary-expr> ::= <decimal> | "(" <expr> ")"
추상 구문 트리
본격적으로 표현식 파싱을 해봅시다! 들어가기 전에, 이 재귀 하향 파서가 뭘 만들어줄지를 결정해야 합니다. 위 그림처럼 엄격하게 BNF을 따르는 파스 트리를 만들어줘도 되지만, 파스 트리는 트리 노드로 "(", "*" 등의 문자까지 포함합니다. 실제로 표현식을 평가하고 싶다면 단순히 정수 리터럴만 잎새 노드에 넣어준 다음 이들끼리 각 연산자나 구문에 맞게 정의한 노드로 이어주기만 해도 평가에 아무 문제 없습니다. 말이 좀 어려운데, -123*(76+5)를 평가하고 싶으면 아래와 같은 트리를 만들면 됩니다.
즉, 전체 표현식은 -123과 (76+5)가 BinMul 노드의 자식으로 들어간 것이고, -123은 정수 리터럴 123을 자식으로 가지는 UnaryMinus 노드입니다. 마찬가지로 (76+5)는 정수 리터럴 76과 5을 자식으로 가지는 BinAdd 노드로 표현됩니다. 이 트리는 추상 구문 트리(Abstract Syntax Tree)라고 하며, 실제 문장에서 나타나는 모든 토큰을 표현하지 않는다는 점에서 파스 트리와 구별됩니다.
따라서 우리가 만들 재귀 하향 파서는 추상 구문 트리를 만들어주면 됩니다. 먼저 각 노드 구조체를 만듭시다. 노드 구조체는 식 평가를 위해 eval이라는 이름의 가상 함수를 가집니다.
// 추상 구문 트리의 가장 베이스가 되는 노드입니다.
// 나머지 노드는 모두 이걸 상속받아 구현합니다.
struct Node {
virtual int eval(void) = 0;
};
// 정수 리터럴에 해당하는 노드입니다. 자식은 없고 정수 값 하나를 멤버로 가집니다.
struct IntLiteral : public Node {
int value;
IntLiteral(int n) : value(n) {}
virtual int eval(void) {
return this->value;
}
};
// 덧셈 연산자에 해당하는 노드입니다. 자식은 둘입니다.
struct BinAdd : public Node {
shared_ptr<Node> left, right;
BinAdd(shared_ptr<Node> l, shared_ptr<Node> r) : left(l), right(r) {}
virtual int eval(void) {
return this->left->eval() + this->right->eval();
}
};
// 뺄셈 연산자입니다.
struct BinSub : public Node {
shared_ptr<Node> left, right;
BinSub(shared_ptr<Node> l, shared_ptr<Node> r) : left(l), right(r) {}
virtual int eval(void) {
return this->left->eval() - this->right->eval();
}
};
// 곱셈 연산자입니다.
struct BinMul : public Node {
shared_ptr<Node> left, right;
BinMul(shared_ptr<Node> l, shared_ptr<Node> r) : left(l), right(r) {}
virtual int eval(void) {
return this->left->eval() * this->right->eval();
}
};
// 단항 + 부호 연산자입니다. 자식은 하나입니다.
struct UnaryPlus : public Node {
shared_ptr<Node> child;
UnaryPlus(shared_ptr<Node> c) : child(c) {}
virtual int eval(void) {
return this->child->eval();
}
};
// 단항 - 부호 연산자입니다.
struct UnaryMinus : public Node {
shared_ptr<Node> child;
UnaryMinus(shared_ptr<Node> c) : child(c) {}
virtual int eval(void) {
return -this->child->eval();
}
};
남은 건 각 비단말 기호별로 함수를 짜는 것 뿐입니다.
using Tokensit = vector<Token>::iterator;
int parse_primary_expr(Tokensit it_begin, Tokensit it_end, shared_ptr<Node> &ast);
int parse_factor(Tokensit it_begin, Tokensit it_end, shared_ptr<Node> &ast);
int parse_term(Tokensit it_begin, Tokensit it_end, shared_ptr<Node> &ast);
int parse_expr(Tokensit it_begin, Tokensit it_end, shared_ptr<Node> &ast);
// <primary-expr>을 파싱하는 함수입니다.
// 성공하면 파싱한 토큰 개수, 실패하면 -1을 리턴합니다.
// 매개 변수 ast로는 파싱이 성공했을 때 만들어진 추상 구문 트리를 전달합니다.
int parse_primary_expr(Tokensit it_begin, Tokensit it_end, shared_ptr<Node> &ast) {
int token_cnt = 0;
// 첫 토큰이 정수 리터럴이면 <decimal>로 파싱 성공입니다.
if (it_begin->type == TokenType::INTEGER) {
ast = make_shared<IntLiteral>(stoi(it_begin->value));
return 1;
}
// 아니라면 첫 토큰은 여는 괄호여야 합니다. 여는 괄호조차 아니면 파싱 실패입니다.
if (it_begin->type == TokenType::PAR_OPEN)
token_cnt++;
else
return -1;
// 그 다음부터 <expr>로 파싱합니다.
token_cnt += parse_expr(it_begin + token_cnt, it_end, ast);
// 마지막은 무조건 닫는 괄호여야죠.
token_cnt++;
// 여기까지 오면 성공.
return token_cnt;
}
// <factor>를 파싱합니다.
int parse_factor(Tokensit it_begin, Tokensit it_end, shared_ptr<Node> &ast) {
int token_cnt = 0, tmp;
shared_ptr<Node> child;
// 먼저 <primary-expr>로 파싱을 시도합니다.
tmp = parse_primary_expr(it_begin, it_end, child);
if (tmp >= 0) {
ast = child;
return tmp;
}
// <primary-expr>이 아니면 첫 번째 토큰은 "+" 또는 "-"입니다.
// 두 번째부터 <factor>로 파싱해줍니다.
token_cnt++;
token_cnt += parse_factor(it_begin + 1, it_end, child);
// child를 자식으로 하는 노드를 만들어서 ast에 넘깁니다.
if (it_begin->type == TokenType::PLUS)
ast = make_shared<UnaryPlus>(child);
else
ast = make_shared<UnaryMinus>(child);
return token_cnt;
}
// <term>을 파싱합니다.
int parse_term(Tokensit it_begin, Tokensit it_end, shared_ptr<Node> &ast) {
int token_cnt = 0;
shared_ptr<Node> left, right;
// <factor>로 파싱합니다.
token_cnt += parse_factor(it_begin, it_end, left);
// 이 다음부터는 ("*" <factor>)가 0개 이상 옵니다.
while (it_begin + token_cnt != it_end
&& (it_begin + token_cnt)->type == TokenType::ASTERISK) {
// "*"가 하나 오고
token_cnt++;
// <factor>로 파싱
token_cnt += parse_factor(it_begin + token_cnt, it_end, right);
// left와 right를 BinMul로 이어줍니다.
left = make_shared<BinMul>(left, right);
}
ast = left;
return token_cnt;
}
// <expr>을 파싱합니다.
int parse_expr(Tokensit it_begin, Tokensit it_end, shared_ptr<Node> &ast) {
int token_cnt = 0;
shared_ptr<Node> left, right;
token_cnt += parse_term(it_begin, it_end, left);
while (it_begin + token_cnt != it_end
&& ((it_begin + token_cnt)->type == TokenType::PLUS
|| (it_begin + token_cnt)->type == TokenType::MINUS)) {
TokenType tp = (it_begin + token_cnt)->type;
token_cnt++;
token_cnt += parse_term(it_begin + token_cnt, it_end, right);
if (tp == TokenType::PLUS)
left = make_shared<BinAdd>(left, right);
else
left = make_shared<BinSub>(left, right);
}
ast = left;
return token_cnt;
}
int main(void) {
string s = "-+(123 + 64 * 7)+ 9*(50 -8 ) ";
vector tokens = tokenize(s);
shared_ptr ast;
parse_expr(tokens.begin(), tokens.end(), ast);
cout << ast->eval();
return 0;
}
출력 결과는 -193입니다.
응용
사실 파싱이란 게 BNF만 잘 정의해주면 함수 짜는 건 노가다라서… 딱히 응용이라 할 것도 없습니다.
BOJ 2504:: 괄호의 값
원래 스택을 쓰면 되는 문제인데 재귀 하향 파서로 풀어봅시다. 문제에서 주어지는 문자열의 문법을 EBNF로 나타내면 다음과 같습니다.
<S> ::= ("()" | "[]" | "(" <S> ")" | "[" <S> "]") <S>?
추상 구문 트리에 노드가 몇 종류 필요한지 세어 봅시다. "()"와 "[]"를 나타내는 노드가 하나씩 필요할 거고(노드 하나에 합쳐도 됩니다), <S> 두 개를 붙여놓는 노드가 필요하고, <S>를 괄호로 감싸는 두 경우에 노드가 하나씩 필요하므로(이것도 합칠 수 있습니다) 5종류가 필요합니다.
#include<bits/stdc++.h>
using namespace std;
enum class TokenType {
PAR_OPEN,
PAR_CLOSE,
PAR_PAIR,
BRA_OPEN,
BRA_CLOSE,
BRA_PAIR,
};
using Tokensit = vector<TokenType>::iterator;
struct Node {virtual int eval(void) = 0;};
struct ParPair : public Node {virtual int eval(void) {return 2;}};
struct BraPair : public Node {virtual int eval(void) {return 3;}};
struct Concat : public Node {
shared_ptr<Node> left, right;
Concat(shared_ptr<Node> l, shared_ptr<Node> r) : left(l), right(r) {}
virtual int eval(void) {
return left->eval() + right->eval();
}
};
struct EnclPar : public Node {
shared_ptr<Node> child;
EnclPar(shared_ptr<Node> c) : child(c) {}
virtual int eval(void) {
return 2 * child->eval();
}
};
struct EnclBra : public Node {
shared_ptr<Node> child;
EnclBra(shared_ptr<Node> c) : child(c) {}
virtual int eval(void) {
return 3 * child->eval();
}
};
vector<TokenType> tokenize(string &s) {
vector<TokenType> res;
for (string::iterator it = s.begin(); it != s.end(); it++) {
switch (*it) {
case ')':
res.push_back(TokenType::PAR_CLOSE); break;
case '(':
if (it + 1 != s.end() && *(it + 1) == ')') {
res.push_back(TokenType::PAR_PAIR);
it++;
}
else
res.push_back(TokenType::PAR_OPEN);
break;
case ']':
res.push_back(TokenType::BRA_CLOSE); break;
case '[':
if (it + 1 != s.end() && *(it + 1) == ']') {
res.push_back(TokenType::BRA_PAIR);
it++;
}
else
res.push_back(TokenType::BRA_OPEN);
break;
default:;
}
}
return res;
}
int parse(Tokensit it_begin, Tokensit it_end, shared_ptr<Node> &ast) {
int token_cnt = 0, tmp;
shared_ptr<Node> left, right;
// 첫 번째 토큰이 "()"거나 "[]"인 경우
if (*it_begin == TokenType::PAR_PAIR) {
token_cnt++;
left = make_shared<ParPair>();
}
else if (*it_begin == TokenType::BRA_PAIR) {
token_cnt++;
left = make_shared<BraPair>();
}
// 첫 번째 토큰이 "("인 경우
else if (*it_begin == TokenType::PAR_OPEN) {
token_cnt++;
// 두 번째부터 재귀적으로 파싱해봅니다.
tmp = parse(it_begin + 1, it_end, left);
// 성공하면 token_cnt를 증가
if (tmp < 0)
return -1;
token_cnt += tmp;
// 마지막은 ")"로 끝나야 합니다.
if (it_begin + token_cnt != it_end && *(it_begin + token_cnt) != TokenType::PAR_CLOSE)
return -1;
token_cnt++;
// 노드를 만듭니다.
left = make_shared<EnclPar>(left);
}
// 첫 번째 토큰이 "["인 경우
else if (*it_begin == TokenType::BRA_OPEN) {
token_cnt++;
tmp = parse(it_begin + 1, it_end, left);
if (tmp < 0)
return -1;
token_cnt += tmp;
if (it_begin + token_cnt != it_end && *(it_begin + token_cnt) != TokenType::BRA_CLOSE)
return -1;
token_cnt++;
left = make_shared<EnclBra>(left);
}
// 나머지는 모두 실패
else
return -1;
// 여기서 문장이 끝나면 파싱 완료입니다.
if (it_begin + token_cnt == it_end) {
ast = left;
return token_cnt;
}
// 이 뒤부터는 <S>가 있거나 없거나 둘 중 하나.
tmp = parse(it_begin + token_cnt, it_end, right);
// 성공하면 left와 right를 이어줍니다.
if (tmp >= 0) {
token_cnt += tmp;
ast = make_shared<Concat>(left, right);
}
// 실패하면 left만 있는 겁니다.
else
ast = left;
return token_cnt;
}
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
string s;
cin >> s;
vector<TokenType> tokens = tokenize(s);
shared_ptr<Node> ast;
int token_cnt = parse(tokens.begin(), tokens.end(), ast);
// 리턴 값이 -1이 아니고 파싱 후 남는 토큰이 없으면 파싱 성공입니다.
// 단순히 리턴 값만 체크하면 "())"같은 입력을 걸러내지 못합니다.
if (token_cnt >= 0 && token_cnt == (int)tokens.size())
cout << ast->eval();
else
cout << 0;
return 0;
}