4.2.3) 소괄호 문제
이제 소괄호를 생각해보자. 다음 중위 표기식을 후위 표기식으로 변환해보라.
1 + 2 * 3
(1 + 2) * 3
1 * (2 + 3)
답은 다음과 같다.
1 + 2 * 3 = 1 2 3 * +
(1 + 2) * 3 = 1 2 + 3 *
1 * (2 + 3) = 1 2 3 + *
알고 있듯이, 소괄호는 중위 표기법으로 표현된 식에서는 연산 순서를 강제로 바꾸는 용도로 쓰인다. 따라서 소괄호가 발견된다면, 이전에 어떤 연산자가 존재하든 관계없이 소괄호가 씌워진 식부터 연산을 진행해야 한다. 즉4.2.2)의 2번 루틴에는 다음 과정이 추가되어야 한다.
1. 여는 소괄호를 만나면, 연산자 보관소에 어떤 연산자가 존재하든 관계없이 여는 소괄호를 보관소에 저장한다.
2. 닫는 소괄호를 만나면, 연산자 보관소에 가장 마지막으로 저장된 여는 소괄호를 발견할 때까지의 모든 연산자를‘후위 표기식’에 출력한다.
다음은 소괄호 문제가 개선된 표기법 변환 프로그램이다.
|
04_in_to_post_paren.cpp |
|
void infix_to_postfix(char *postfix, const char *infix) { // 첫 문자가 수인지 확인하는 코드 삭제 char ch; Stack opStack; // operator stack for (ch = *infix; (ch = *infix) != '\0'; ++infix) { if (is_digit(ch)) { while (is_digit(*infix)) { *postfix++ = *infix++; } --infix; // 반복문 재실행시 ++infix가 실행되므로 한 칸 되돌린다 } else { // is_operator if (ch == '(') { // 여는 괄호라면 그냥 넣는다 opStack.push(ch); } else if (ch == ')') { // 닫는 괄호를 발견한 경우의 처리 if (opStack.is_empty() == false) { // get operator priority while (opStack.is_empty() == false) { char top = opStack.top(); if (top == '(') { // 여는 괄호를 찾았다면 종료 break; } else { // 우선순위가 낮은 연산자를 스택에서 꺼내 // 후위 표기식에 추가 *postfix++ = opStack.pop(); } } // 올바른 괄호 쌍이 존재하는지 확인 if (opStack.top() != '(') { throw Exception("Invalid parenthesis"); } // 스택에 있는 여는 소괄호를 버린다 opStack.pop(); } } else { if (opStack.is_empty() == false) { // get operator priority int new_pri = op_pri(ch); while (opStack.is_empty() == false) { char top = opStack.top(); if (top == '(') { // 여는 괄호를 찾았다면 종료 break; } else if (new_pri <= op_pri(top)) { *postfix++ = opStack.pop(); } else { break; } } } opStack.push(ch); } } } // 스택에 남은 연산자를 while (opStack.is_empty() == false) { char op = opStack.pop(); if (op == '(') { // 위에서 처리되지 않은 소괄호가 있다면 예외 throw Exception("Invalid parenthesis"); } *postfix++ = op; } *postfix = '\0'; } |
이와 같이 소괄호 문제를 해결할 수 있었다.
