수식 파싱¶
숫자와 여러 연산자로 이루어진 수식을 담은 문자열이 주어집니다. 이 수식의 값을 $O(n)$에 계산해야 합니다. 여기서 $n$은 문자열의 길이입니다.
여기서 다루는 알고리즘은 수식을 이른바 역폴란드 표기법으로 (명시적으로든 암묵적으로든) 변환한 뒤 그 수식의 값을 계산합니다.
역폴란드 표기법¶
역폴란드 표기법은 연산자를 피연산자 뒤에 두는 수식 표기 방식입니다. 예를 들어 다음 수식은
역폴란드 표기법으로 다음과 같이 쓸 수 있습니다.
역폴란드 표기법은 1920년에 폴란드 수학자 Jan Łukasiewicz가 제안한 폴란드 표기법을 바탕으로, 1950년대 중반에 오스트레일리아의 철학자이자 컴퓨터 과학 전문가인 Charles Hamblin이 개발했습니다.
역폴란드 표기법의 장점은 이 형태로 된 수식을 선형 시간에 매우 쉽게 계산할 수 있다는 점입니다. 처음에는 비어 있는 스택을 하나 사용합니다. 역폴란드 표기법으로 된 수식의 피연산자와 연산자를 차례로 순회합니다. 현재 원소가 숫자이면 그 값을 스택 맨 위에 넣고, 현재 원소가 연산자이면 스택 맨 위의 두 원소를 꺼내 연산을 수행한 뒤 그 결과를 다시 스택 맨 위에 넣습니다. 마지막에는 스택에 원소가 정확히 하나 남으며, 그 값이 수식의 값입니다.
이 단순한 계산이 $O(n)$ 시간에 동작한다는 것은 자명합니다.
단순한 수식의 파싱¶
당분간은 단순화한 문제만 생각합니다. 모든 연산자가 이항 연산자(즉, 인자를 두 개 받음)이고, 모두 좌결합(우선순위가 같으면 왼쪽에서 오른쪽으로 실행됨)이라고 가정합니다. 괄호는 사용할 수 있습니다.
스택을 두 개 준비합니다. 하나는 숫자용이고, 다른 하나는 연산자와 괄호용입니다. 처음에는 두 스택 모두 비어 있습니다. 두 번째 스택에서는 모든 연산이 우선순위의 엄격한 내림차순으로 정렬되어 있다는 조건을 유지합니다. 스택에 괄호가 있으면 (괄호 한 쌍에 대응하는) 각 연산자 블록은 정렬되어 있지만, 스택 전체가 반드시 정렬되어 있는 것은 아닙니다.
수식의 문자를 왼쪽에서 오른쪽으로 차례로 순회합니다. 현재 문자가 숫자이면 그 수의 값을 스택에 넣습니다. 현재 문자가 여는 괄호이면 그것을 스택에 넣습니다. 현재 문자가 닫는 괄호이면 여는 괄호에 도달할 때까지 스택에 있는 모든 연산자를 실행합니다(즉, 괄호 안의 모든 연산을 수행합니다). 마지막으로 현재 문자가 연산자이면 스택 맨 위에 우선순위가 같거나 더 높은 연산자가 있는 동안 그 연산을 실행하고, 그런 다음 새 연산을 스택에 넣습니다.
문자열 전체를 처리한 뒤에도 스택에 연산자가 남아 있을 수 있으므로 그것들을 실행합니다.
다음은 네 연산자 $+$ $-$ $*$ $/$에 대해 이 방법을 구현한 것입니다.
bool delim(char c) {
return c == ' ';
}
bool is_op(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
int priority (char op) {
if (op == '+' || op == '-')
return 1;
if (op == '*' || op == '/')
return 2;
return -1;
}
void process_op(stack<int>& st, char op) {
int r = st.top(); st.pop();
int l = st.top(); st.pop();
switch (op) {
case '+': st.push(l + r); break;
case '-': st.push(l - r); break;
case '*': st.push(l * r); break;
case '/': st.push(l / r); break;
}
}
int evaluate(string& s) {
stack<int> st;
stack<char> op;
for (int i = 0; i < (int)s.size(); i++) {
if (delim(s[i]))
continue;
if (s[i] == '(') {
op.push('(');
} else if (s[i] == ')') {
while (op.top() != '(') {
process_op(st, op.top());
op.pop();
}
op.pop();
} else if (is_op(s[i])) {
char cur_op = s[i];
while (!op.empty() && priority(op.top()) >= priority(cur_op)) {
process_op(st, op.top());
op.pop();
}
op.push(cur_op);
} else {
int number = 0;
while (i < (int)s.size() && isalnum(s[i]))
number = number * 10 + s[i++] - '0';
--i;
st.push(number);
}
}
while (!op.empty()) {
process_op(st, op.top());
op.pop();
}
return st.top();
}
이렇게 해서 수식의 값을 $O(n)$에 계산하는 방법을 배웠으며, 이 과정에서 역폴란드 표기법을 암묵적으로 사용했습니다. 위 구현을 조금 수정하면 역폴란드 표기법으로 된 수식을 명시적인 형태로 얻을 수도 있습니다.
단항 연산자¶
이제 식에 단항 연산자(인수를 하나만 받는 연산자)도 포함되어 있다고 가정해 봅시다. 단항 플러스와 단항 마이너스가 이러한 연산자의 대표적인 예입니다.
이 경우의 차이점 중 하나는 현재 연산자가 단항 연산자인지 이항 연산자인지 판별해야 한다는 것입니다.
단항 연산자 앞에는 항상 다른 연산자나 여는 괄호가 있거나, (식의 맨 처음에 있는 경우) 아무것도 없다는 것을 알 수 있습니다. 반대로 이항 연산자 앞에는 항상 피연산자(수)나 닫는 괄호가 있습니다. 따라서 다음 연산자가 단항 연산자일 수 있는지 여부를 쉽게 표시할 수 있습니다.
또한 단항 연산자와 이항 연산자는 서로 다르게 실행해야 합니다. 그리고 단항 연산자의 우선순위를 모든 이항 연산자보다 높게 정해야 합니다.
덧붙여 일부 단항 연산자(예: 단항 플러스와 단항 마이너스)는 실제로 우결합이라는 점에 유의해야 합니다.
우결합성¶
우결합이란 우선순위가 같을 때마다 연산자를 오른쪽에서 왼쪽으로 계산해야 한다는 뜻입니다.
앞에서 언급했듯이 단항 연산자는 보통 우결합입니다. 우결합 연산자의 또 다른 예로는 거듭제곱 연산자가 있습니다($a \wedge b \wedge c$는 보통 $(a^b)^c$가 아니라 $a^{b^c}$로 받아들여집니다).
우결합 연산자를 올바르게 처리하려면 무엇을 달리해야 합니까? 알고 보면 변경 사항은 매우 적습니다. 유일한 차이점은 우선순위가 같을 때 우결합 연산의 실행을 뒤로 미룬다는 것입니다.
바꿔야 하는 줄은 다음 한 줄뿐입니다.
while (!op.empty() && priority(op.top()) >= priority(cur_op))
while (!op.empty() && (
(left_assoc(cur_op) && priority(op.top()) >= priority(cur_op)) ||
(!left_assoc(cur_op) && priority(op.top()) > priority(cur_op))
))
left_assoc는 연산자가 left_associative인지 아닌지를 판단하는 함수입니다.
다음은 이항 연산자 $+$ $-$ $*$ $/$와 단항 연산자 $+$ 및 $-$에 대한 구현입니다.
bool delim(char c) {
return c == ' ';
}
bool is_op(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
bool is_unary(char c) {
return c == '+' || c=='-';
}
int priority (char op) {
if (op < 0) // unary operator
return 3;
if (op == '+' || op == '-')
return 1;
if (op == '*' || op == '/')
return 2;
return -1;
}
void process_op(stack<int>& st, char op) {
if (op < 0) {
int l = st.top(); st.pop();
switch (-op) {
case '+': st.push(l); break;
case '-': st.push(-l); break;
}
} else {
int r = st.top(); st.pop();
int l = st.top(); st.pop();
switch (op) {
case '+': st.push(l + r); break;
case '-': st.push(l - r); break;
case '*': st.push(l * r); break;
case '/': st.push(l / r); break;
}
}
}
int evaluate(string& s) {
stack<int> st;
stack<char> op;
bool may_be_unary = true;
for (int i = 0; i < (int)s.size(); i++) {
if (delim(s[i]))
continue;
if (s[i] == '(') {
op.push('(');
may_be_unary = true;
} else if (s[i] == ')') {
while (op.top() != '(') {
process_op(st, op.top());
op.pop();
}
op.pop();
may_be_unary = false;
} else if (is_op(s[i])) {
char cur_op = s[i];
if (may_be_unary && is_unary(cur_op))
cur_op = -cur_op;
while (!op.empty() && (
(cur_op >= 0 && priority(op.top()) >= priority(cur_op)) ||
(cur_op < 0 && priority(op.top()) > priority(cur_op))
)) {
process_op(st, op.top());
op.pop();
}
op.push(cur_op);
may_be_unary = true;
} else {
int number = 0;
while (i < (int)s.size() && isalnum(s[i]))
number = number * 10 + s[i++] - '0';
--i;
st.push(number);
may_be_unary = false;
}
}
while (!op.empty()) {
process_op(st, op.top());
op.pop();
}
return st.top();
}