[93일차]후위 표기식 - 백준 - 1918(python - 자료구조, 스택)

문제 설명

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

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

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

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

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

결과: ABC*+DE/-

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

 

입력

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

 

출력

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

 

예제 입력, 예제 출력

A*(B+C)	ABC+*
A+B	AB+
A+B*C	ABC*+
A+B*C-D/E	ABC*+DE/-

 

코드 및 설명

s = input()
stack = []
answer = ""

for char in s:  
  # char.isalpha()
  if char not in ('*','/', '(', ')', '+', '-'):
    answer += char  
  else:
    if char == '(':
      stack.append(char)
    elif char == "*" or char == "/":
      while stack and ( stack[-1] == "*" or stack[-1] == "/"):
        answer += stack.pop()      
      stack.append(char)
    elif char == "+" or char == "-":
      while stack and stack[-1] != "(":
        answer += stack.pop()      
      stack.append(char)
    elif char == ")":
      while stack and stack[-1] != "(":
        answer += stack.pop()  
      stack.pop()
   
while stack:
  answer += stack.pop()
  
print(answer)

 

이 문제는 후위 표기식을 만드는 문제인데 스택을 이용하여 풀었다. 

 

A * (B+C)

A * BC+

ABC+*

 

이런식으로 후위 표기식으로 바꾸는 것이다. 위에 ABC+*은 B와 C를 더 한 것에 A 곱한다라는 말이다.

 

A+B*C-D/E --> 괄호를 만들어보면

 

( A + ( B * C ) ) - (D / E) --> 이런식으로 나오는데

( A + BC* ) - DE/

ABC*+ - DE/

ABC*+DE/-  

 

BC를 곱한 것에 A를 더하고, D와 E를 나눈 것에서 빼기를 해준다. 라는 말이다.

 

이제 이 것을 코드로 바꾸면 된다. 처음에 알파벳인지 아니면 '*','/', '(', ')', '+', '-' 인지 구분을 지어줘야하기 때문에 

 

if char not in ('*','/', '(', ')', '+', '-') 혹은 char.isalpha()로 사용 가능한다. isalpha는 대문자알파벳이면 1, 소문자면 2

 

아니면 0을 반환한다.

 

제일 처음으로 확인해야하는 것이 '(' 이 괄호가 열렸을 땐 stack에 append만 해주면 된다. ( 괄호가 열렸다는 건

 

안에 있는 값이 먼저 계산되어야하는 것.

 

A * (B+C) <-- 이 예제로 설명을 해보겠다.

 

A

answer =  'A'

stack = [] 

 

정답에는 A가 들어가고 stack은 비어있는 상태

 

* 

answer = 'A'

stack = [ '*' ]

 

알파벳이 아니기 때문에 else문을 타고 곱셉 표시지만 stack에 값이 없기때문에 stack 넣어주고 넘어간다.

 

(

answer = 'A'

stack = [ '*', '(' ]

 

'('는 stack 넣어주기만 하면 된다.

 

B

answer = 'AB'

stack = [ '*', '(' ]

 

알파벳이니까 answer 더해준다.

 

+

answer = 'AB'

stack = [ '*' , '(' , '+' ] 

 

stack은 비어있지 않으나 stack Top에 해당하는 값이 '('이기때문에 쌓기만 한다.

 

C

answer = 'ABC'

stack = [ '*' , '(' , '+' ]

 

알파벳 더해주고

 

)

answer = 'ABC+'

stack = [ '*' ]

 

stack이 비어있지 않고 stack Top에 해당하는 값이 '(' 아니기 때문에 answer에 stack.pop()한 것을 쌓아주고, 

 

그 다음은 값은 '('이기 때문에 stack.pop()을 해준다.

 

그럼 여기서 stack 값이 남아있는 데 이것을 while을 돌려서 stack에 top부터 차근차근 빼오면서 answer에 붙여준다.

 

그럼 정답이 나오게 된다.