중위 표기법과 후위 표기법
중위 표기법 (infix notation)
- 우리가 일상에서 사용하는 수식의 표기법
- 연산자가 피연산자들의 사이에 위치
(A + B) * (C + D)
후위 표기법 (postfix notation)
- 컴퓨터가 수식을 계산하는데 유리함
- 연산자가 피연산자들의 뒤에 위치
AB+CD+*
중위 표기법 수식을 후위 표기법 수식으로 변환하는 알고리즘을 스택으로 구현할 수 있다.
중위 표현식 –> 후위 표현식
- [중위] A * B + C
- [후위] A B * C +
처음 만나는 피연산자는 그냥 적는다. 다음 만나는 * 연산자는 일단 스택에 넣는다. 그리고 다음에 표현되는 피 연산자 B도 처음과 같이 그대로 적는다. 여기서 중요하다. 이 때 만나는 + 연산자와 이미 스택에 있는 * 연산자와 비교를 해본다. *의 우선 순위가 높기 때문에 pop 해서 적는다. 그리고 +의 연산자는 스택에 넣도록 한다. C 역시 피연산자 이므로 그대로 적고 + 연산자를 pop하면 중위 표현식에서 후위 표현식으로 바꾸는 것이 완료된다.
- [중위] A + B * C
- [후위] A B C * +
A는 그대로 적고 + 연산자는 스택에 넣는다. B도 그대로 뒤에 적고 * 연산자를 + 연산자와 비교하고 우선 순위가 높은 *를 스택에 그대로 넣는다. 다음 C 연산자를 적고 연산자를 후위선출 방식으로 pop하면 *, + 순서대로 뒤에 적으면 후위 표현식이 완성된다.
- [중위] A + B + C
- [후위] A B + C +
연산자가 같을 떄는 첫 번째 예제처럼 먼저 pop하고 다음 연산자를 스택에 넣는 방법으로 한다.
괄호의 처리
- [중위] (A + B) * C
- [후위] A B + C *
괄호는 무조건 우선순위가 되어야 한다. 따라서 여는 괄호를 만나면 스택에 push하고 닫는 괄호를 만나면 여는 괄호가 나올 때 까지 pop을 하는 방식으로 한다.
- [중위] A * (B + C)
- [후위] A B C + *
코딩으로 옮길 때는 ( (여는 괄호)의 우선 순위를 가장 낮게 설정하여 +, * 등이 pop되지 않도록 하는 것이 포인트
다음 예제들도 위에서 설명한 방법으로 적용하면 쉽게 후위 표현식으로 바꿀 수 있다.
Q. 1)
- [중위] (A + B) * (C + D)
- [후위] A B + C D + *
Q. 2)
- [중위] (A + (B - C)) * D
- [후위] A B C - + D *
Q. 3)
- [중위] A * (B - (C + D))
- [후위] A B C D + - *
알고리즘 설계하기
연산자의 우선순위 설정
prec = { ‘*’ : 3, ‘/’ : 3, ‘+’ : 2, ‘-‘ : 2, ‘(‘ : 1, }
중위 표현식을 왼쪽부터 한 글자씩 읽기
- 피연산자이면 그냥 출력
- ’(‘이면 스택에 push
- ’)’이면 ‘(‘이 나올 때까지 스택에서 pop하고 출력
- 연산자이면 스택에서 높거나 같은 우선순위 것들을 pop하고 출력
class ArrayStack:
def __init__(self):
self.data = []
def size(self):
return len(self.data)
def isEmpty(self):
return self.size() == 0
def push(self, item):
self.data.append(item)
def pop(self):
return self.data.pop()
def peek(self):
return self.data[-1]
prec = {
'*': 3, '/': 3,
'+': 2, '-': 2,
'(': 1, ')': 1,
}
def solution(S):
opStack = ArrayStack()
temp = list()
answer = ''
for i in S:
print(i)
if i not in prec:
answer += i
print('피연산자', i)
elif i == ')':
temp.pop()
while opStack.isEmpty() == False:
answer += opStack.pop()
print('연산자 pop')
elif i == '(' or '(' in temp:
if i == '(':
temp.append(i)
else:
opStack.push(i)
print('연산자 push', i)
else:
if opStack.isEmpty():
opStack.push(i)
print('연산자 push', i)
elif prec[opStack.peek()] >= prec[i]:
answer += opStack.pop()
print('연산자 pop', i)
opStack.push(i)
print('연산자 push', i)
else:
opStack.push(i)
print('연산자 push', i)
if not opStack.isEmpty():
while opStack.isEmpty() == False:
answer += opStack.pop()
print('연산자 pop')
return answer
6개 중 1개의 테스트 케이스에서 계속 실패함. 추후 업데이트.
Comments