개발 학습 블로그입니다.

4 minute read

백준 문제 중 1918번

https://www.acmicpc.net/problem/1918

문제

수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다.

이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하면 순서를 적절히 조절하여 순서를 정해줄 수 있다. 또한 같은 방법으로 괄호 등도 필요 없게 된다. 예를 들어 a+bc를 후위 표기식으로 바꾸면 abc+가 된다.

중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설명하면 이렇다. 우선 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. 그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.

예를 들어 a+bc는 (a+(bc))의 식과 같게 된다. 그 다음에 안에 있는 괄호의 연산자 를 괄호 밖으로 꺼내게 되면 (a+bc)가 된다. 마지막으로 또 +를 괄호의 오른쪽으로 고치면 abc*+가 되게 된다.

다른 예를 들어 그림으로 표현하면 A+B*C-D/E를 완전하게 괄호로 묶고 연산자를 이동시킬 장소를 표시하면 다음과 같이 된다.

img

이러한 사실을 알고 중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오

입력

첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다.

출력

첫째 줄에 후위 표기식으로 바뀐 식을 출력하시오

풀이

처음 문제를 봤을때 문자열을 스캔하되 사칙연산에 우선순위를 두고 곱하기나 나누기가 나온다면 스택에 있던 연산자를 모두 붙이고 다시 진행하고 만약 괄호를 만나다면 괄호 안에 있는 문자를 다시 재귀로 호출 하는 식으로 프로그램을 생각했었다.

근데 생각대로 잘 구현이 되지 않아서 거의 하루종일 고민을하다 검색을 통해 힌트를 얻었다.

Try1

중위표현식으로 이루어진 midfixs를 스캔하며 진행한다.

  1. 스캔중인 문자i 가 알파벳이라면 바로 ans 에 더해준다.
  2. 스캔중인 문자i 가 알파벳이 아니고 ‘(‘ 라면 바로 스택 stk에 넣는다.
  3. 스캔중인 문자 i가 ‘ * , / ‘이며 스택stk이 비어있다면 스택stk에 추가하고, 스택stk가 차있고 스택stk의 top이 ‘ * ‘ 나 ‘/’면 스택stk에 차있던(연산 우선순위가 같고, 먼저 해야하는 연산이므로) ‘ * , / ‘ 가 연산 순서에 맞게 먼저 소비되어야 하므로 스택stk가 빌때까지 ans 에 더해주고 스택stk을 모두 비우면 다시 스캔중인 문자 i를 스택stk에 넣어준다.
  4. 스캔중인 문자 i가 ‘+-‘이며 스택stk이 비어있다면 스택stk에 추가하고 스택stk가 차있다면(연산 우선순위가 같고, 먼저 해야되는 연산이므로) 스택의 top stk[-1]이 ‘(‘ 가 아닐때까지 ans에 더해주고 스택이 모두 비거나 ‘(‘가 아직 스택에 남아 있다면 스캔중인 문자 i를 스택stk에 추가
  5. 스캔중인 문자 i가 ‘)’라면 스택 stk의 top stk[-1]이 ‘(‘ 일때까지 ans에 더해준 뒤 마지막 원소는 ‘(‘이므로 스택stk 에서 pop해준다.
  6. 스택stk에 연산자가 남아있다면 빌때까지 ans에 더해준다.
midfixs = input()
stack = []
ans = ''

for i in midfixs:

     # 알파벳이면 바로 ans에 더함
    if i.isalpha():
        ans += i 
    else:
        print(f'stk:{stack}')

         # '(' 는 바로 스택에 넣음
        if i == '(':
            stack.append(i)

         # 스택이 비거나 스택의 top이 '*/'가 아니라면 스택에 추가(먼저 연산 할 필요가없음)
        elif i in '*/':
            while stack and (stack[-1] == '*' or stack[-1] == '/'):
                ans += stack.pop()
            stack.append(i)

         # '+-'가 스택에 없다면 추가, 스택이 비거나 '(' 를 만날때까지 ans에 더해줌
        elif i in '+-':
            while stack and stack[-1] != '(':
                ans += stack.pop()
            stack.append(i)

         # ')'라면 스택의'('를 만날때까지 ans에 더해준뒤 '('는 제거
        elif i == ')':
            while stack and stack[-1] != '(':
                ans += stack.pop()
            stack.pop()

 # 모든 문자 스캔을 마치고 남은 스택을 ans에 더해줌          
while stack:
    ans += stack.pop()
print(ans)

A+(B+C)*D
stk:[]
stk:['+']
stk:['+', '(']
stk:['+', '(', '+']
stk:['+']
ABC+D*+

이렇게 문제를 해결했으나 코드가 직관적이지 않다는 생각이 들었고, 이 풀이에서 힌트를 얻어 처음 생각 했던대로 연산에 우선순위를 두어 코드를 구성해봤다

Try2

연산자의 우선순위 정보를 딕셔너리 priority에 선언하고 현재 스캔중인 연산자의 우선순위 더 높으면 스택에 추가 낮으면 스택에 있던 연산부터 문자열에 더하는 식으로 진행한다.

midfixs = input()

prority = {'*':3,'/':3,'+':2,'-':2,'(':1}
operand =''
operator = []

for midfix in midfixs:

     # midfix가 알파벳이면 operand에 추가
    if midfix.isalpha():
        operand+=midfix

     # midfix가 '(' 라면 operator 스택에 추가
    elif midfix == '(':
        operator.append(midfix)

     # midfix가 사칙연산중에 하나일따
    elif midfix in '+-*/':

         # 스택이 비었다면 바로 추가
        if not operator:
            operator.append(midfix)

         # 스택operator 최상단 원소의 우선순위가
         # 현재 스캔중인 문자열의 우선순위보다 높거나 같을때
        elif priority[operator[-1]]>=priority[midfix]:
            while operator and operator[-1]!='(':
                operand+=operator.pop()
            operator.append(midfix)

         # 낮다면 midfix를 operator에 추가
        else:
            operator.append(midfix)

     # ')' 를 만나면 '(' 를 만날때까지 operand에 추가
    elif midfix == ')':
        while operator and operator[-1]!='(':
            operand+=operator.pop()
        operator.pop()
        

    print(f'operand:{operand}')
    print(f'operator:{operator}')
    

while operator:
    operand+=operator.pop()

print(operand)

(A+(B+C)*D+C)*E
operand:
operator:['(']
operand:A
operator:['(']
operand:A
operator:['(', '+']
operand:A
operator:['(', '+', '(']
operand:AB
operator:['(', '+', '(']
operand:AB
operator:['(', '+', '(', '+']
operand:ABC
operator:['(', '+', '(', '+']
operand:ABC+
operator:['(', '+']
operand:ABC+
operator:['(', '+', '*']
operand:ABC+D
operator:['(', '+', '*']
operand:ABC+D*+
operator:['(', '+']
operand:ABC+D*+C
operator:['(', '+']
operand:ABC+D*+C+
operator:[]
operand:ABC+D*+C+
operator:['*']
operand:ABC+D*+C+E
operator:['*']
ABC+D*+C+E*

배운점

스택이 활용되는 대표적인 문제로서 컴퓨터가 사칙연산을 처리할때 어떻게 순서대로 계산을 할 수 있었는지 알게되었고, 스택 을 다룰때의 패턴이나 요량들을 알 수 있었다.

Leave a comment

You may also enjoy