후위 표기식

#1935 https://www.acmicpc.net/problem/1935

1935번: 후위 표기식2

 

후위표기식이라는 새로운 개념을 만났다. 기존의 수학 표기법은 중위표기식 이라고 하는데

A + (B*C) - D/E 이렇게 연산자(기호)가 피연산자(수) 사이에 위치한다.

반면에 후위 표기식은 연산자가 피연산자 뒤에 위치하는데, 위 식과 동일한 형태의 식이

ABC*+DE/- 이다.

 

어떻게 처리하나 고민을 많이 했지만, 역시나 Stack을 사용하면 됐다.

기호가 나오기 전 까지 수를 stack에 저장하고, 기호가 나오면 pop을 두번 진행해 나온 수를 가지고 연산한다.

그 결과를 다시 stack의 top에 저장해주면 된다.

 

어려웠던 부분은 stack보다도 알파벳으로 들어온 공식에 숫자를 대입해주는 방법이였는데,

ord()라는 함수를 사용하면 됐다.

ord() 함수는 chr()함수와 반대되는 기능을 가지는데

해당 값의 유니코드 값을 리턴한다. (chr은 유니코드를 문자로 바꿔준다.)

 

즉 ord() : 문자 -> 숫자

    chr() : 숫자 -> 문자

순서대로 변환할 수 있다.

print(ord("A")) # return 65
print(chr(ord("A"))) # retrun A

이 기능들을 이용해서 알파벳을 순서대로 list index로 대입해 줄 수 있었다.

 

따라서 후위표기식을 계산하는 코드는 다음과 같다.

N = int(input())
S = input().strip()

nums = [int(input()) for i in range(N)]
stack = []
for s in S:
    if ord("A") <= ord(s) <= ord("Z"):
        stack.append(nums[ord(s) - 65])
    else:
        num1, num2 = stack.pop(), stack.pop()
        if s == "*":
            stack.append(num2*num1)
        elif s == "/":
            stack.append(num2/num1)
        elif s == "+":
            stack.append(num2+num1)
        elif s == "-":
            stack.append(num2-num1)

print("{:.2f}".format(stack.pop()))

 

+) format도 좀 익숙해지자! { [전체길이] . [소수점 이하 길이] [타입] }.format(value)

길이 값이 없을 때에는 : 기호를 넣어주면 된다.

타입은 s, f  정도만 알면 될 듯!

 

 

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

1918번: 후위 표기식

위 문제와 조금 다르다. 중위표기식인 입력값을 후위표기식으로 변환하는 코드이다.

제일 중요한 개념은 연산 우선순위를 체크하는건데

 

최우선 -> ( )

우선    -> *   /

차선    -> +  -

 

이 문제 역시나 스택을 이용한다.

후위표기식은 피연산자를 우선해서 적고 뒤에 연산자를 작성하는 방식이기 때문에 피연산자는 바로 출력하고 연산자를 stact에 넣은 뒤 조건에 맞춰서 pop하면 된다.

가능한 기호의 경우는 ( , ) , * , / , + , - , 총 6가지 경우인데, 각각의 경우에 대해서 생각해보자

 

1. ( : 여는괄호
   • 여는 괄호는 최우선으로 연산해야하는 식을 의미한다. 때문에 아무 값도 pop하지 않고 스택에 쌓는다.
2. ) : 닫는괄호
   • 닫는 괄호의 경우에는 다르다. 괄호 안의 식이 끝났다는 의미이므로 stack의 top에 여는괄호 ( 가 올 때까지 모든 연산자를 pop한다.
3. * , / : 곱셈과 나눗셈
   • 곱셈과 나눗셈은 사칙연산 중 우선순위가 높다. 때문에 stack의 top에 + 또는 -가 올 때까지 pop한다. 그 후 현재 연산자를 stack에 쌓는다.
4. + , - : 덧셈과 뺄셈
   • 가장 우선순위가 낮다. 때문에 stack의 top에 여는 괄호 ( 가 올 때만 제외하고 전부 pop을 해준다. 그 뒤 현재 연산자를 stack에 쌓는다.

핵심 개념은 현재 문자가 stack top에 있는 문자보다 우선순위가 더 높거나 같을 경우에는 출력을 해준다는 부분이다.

곱셈, 나눗셈이 나올 때에는 곱셈과 나눗셈만

덧셈, 뺄셈이 나오면 여는 괄호가 나올 때가지 (없다면 무시) 전부 출력해준다.

 

조금 이해하기 어려웠지만 조금은 익숙해진 기분이다.

S = input().strip()

stack = []
answer = ""

# 조건부 pop

for s in S:
    if s == "(":  # pop 불가능
        stack.append(s)
    elif s == ")":  # ( 가 나올 때까지 pop
        while stack[-1] != "(":
            answer += stack.pop()
        stack.pop()
    elif s == "*" or s == "/":  # 현재 문자의 우선순위가 더 높거나 같을 경우에만 pop # ( 제외
        if len(stack) == 0:
            stack.append(s)
            continue

        while len(stack) > 0 and stack[-1] in ["/", "*"]:
            answer += stack.pop()
        stack.append(s)

    elif s == "+" or s == "-":  # 현재 문자의 우선순위가 더 높거나 같을 경우에만 pop # ( 제외
        if len(stack) == 0:
            stack.append(s)
            continue

        while len(stack) > 0 and stack[-1] in ["+", "-", "*", "/"]:
            answer += stack.pop()
        stack.append(s)
    else: # 이외의 경우 -> 피연산자일 경우에 그냥 출력
        answer += s

while len(stack) > 0:
    answer += stack.pop()
print(answer)