스택과 계산기

소괄호 문제

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';

}

이와 같이 소괄호 문제를 해결할 수 있었다.

댓글

댓글 본문
버전 관리
한도영
현재 버전
선택 버전
graphittie 자세히 보기