스택의 괄호 검사
1. 개요
- 스택의 괄호 검사
▪ 수식에 포함되어 있는 괄호는 가장 마지막에 열린 괄호를 가장 먼저 닫아 주어야 하는 후입선출 구조로 구성되어 있음 ▪ 후입선출 구조의 스택을 이용하여 괄호를 검사함
▪ 수식을 왼쪽에서 오른쪽으로 하나씩 읽으면서 괄호 검사
① 왼쪽 괄호를 만나면 스택에 Push
② 오른쪽 괄호를 만나면 스택을 Pop하여 마지막에 저장한 괄호와 같은 종류인지를 확인
- 같은 종류의 괄호가 아닌 경우 괄호의 짝이 잘못 사용된 수식임
▪ 수식에 대한 검사가 모두 끝났을 때 스택은 공백 스택이 됨
- 수식이 끝났어도 스택이 공백이 되지 않으면 괄호의 개수가 틀린 수식임
2. 알고리즘
- 괄호의 쌍 검사 알고리즘
testPair( )
exp ← Expression;
Stack ← null;
while (true) do { // 무한 루프 (아래 retrun문에서 빠져 나옴)
Symbol ← getSymbol(exp);
Case {
Symbol = “(” or “[” or “{” : // 열린 괄호인 경우
Push(Stack, symbol): // 스택에 push
Symbol = “)”: // 닫힌 괄호가 “)”인 경우
open_pair ← pop(Stack): // 스택에서 pop
If (open_pair ≠ “(”) then return false; // 같은 종류의 괄호가 아닌 경우 괄호의 짝이 잘못 사용된 수식이므로 false로 리턴
symbol = “]”:
open_pair ← pop(Stack): // 스택에서 pop
if (open_pair ≠ “[”) then return false;
symbol = “}”:
open_pair ← pop(Stack): // 스택에서 pop
if (open_pair ≠ “{”) then return false;
symbol = null: // 수식이 끝난 경우
if (isEmpty(Stack)) then return true; //수식이 끝났어도 스택이 공백이 되지 않으면 괄호의 개수가 틀린 수식이므로 false로 리턴
else return false;
else:
}
}
end testPair( )
수식의 표기법 변환
1. 수식의 표기법
- 전위 표기법(Prefix Notation)
▪ 연산자를 피연산자를 앞에 표기하는 방법
예) +AB
- 중위 표기법(Infix Notation)
▪ 연산자를 피연산자의 가운데 표기하는 방법
예) A+B
- 후위 표기법(Postfix Notation)
▪ 연산자를 피연산자의 뒤에 표기하는 방법
예) AB+
2. 변환 방법
- 중위 표기식의 전위 표기식 변환 방법
① 수식의 각 연산자에 대해서 우선 순위에 따라 괄호를 사용하여 다시 표현함
② 각 연산자를 그에 대응하는 왼쪽 괄호의 앞으로 이동시킴
③ 수식의 괄호를 제거함
예) A*B-C/D
▪ 1단계: ( (A*B) - (C/D) )
▪ 2단계: -( *(AB) / (CD) )
▪ 3단계: -*AB / CD
- 중위 표기식의 후위 표기식 변환 방법
① 수식의 각 연산자에 대해서 우선 순위에 따라 괄호를 사용하여 다시 표현함
② 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킴
③ 수식의 괄호를 제거함
예) A*B-C/D
▪ 1단계: ( (A*B) - (C/D) )
▪ 2단계: ( (AB) * (CD)/ )-
▪ 3단계: AB * CD/-
- 중위 표기식의 후위 표기식 변환 알고리즘
① 왼쪽 괄호를 만나면 무시하고 다음 문자를 읽음
② 피연산자를 만나면 출력함
③ 연산자를 만나면 스택에 Push함
④ 오른쪽 괄호를 만나면 스택을 Pop하여 출력함
⑤ 수식이 끝나면, 스택이 공백이 될 때까지 Pop하여 출력함
- 스택을 사용한 후위 표기식 변환 과정
예) A*B-C/D
수식의 후위 표기식 연산
1. 연산 방법
- 수식의 후위 표기식 연산 방법
① 피연산자를 만나면 스택에 Push함
② 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 Pop하여 연산하고, 연산 결과를 다시 스택에 Push함
③ 수식이 끝나면, 마지막으로 스택을 Pop하여 출력함
* 수식이 끝나고 스택에 마지막으로 남아있는 원소는 전체 수식의 연산결과 값이 됨
2. 알고리즘
- 후위 표기 수식의 연산 알고리즘
evalPostfix(exp)
While (true) do {
symbol ← getSymbol(exp);
case {
symbol = operand: // 피연산자 처리
push(Stack, symbol);
symbol = operator: // 연산자 처리
opr2 ← pop(Stack);
opr1 ← pop(Stack);
result ← opr1 op(symbol) opr2; // 스택에서 꺼낸 피연산자들을 연산자로 연산
push(Stack, result);
symbol = null: // 후위 수식의 끝
print(pop(Stack));
}
}
end evalPostfix( )