20129번: 뒤집힌 계산기 (구현, 후위표현법)

 

20129번: 뒤집힌 계산기

이 문제는 중위표현법을 후위표현법으로 나타내는 단순 구현문제이다. 

---

0. 중위표현법을 후위표현법으로 나타내기 / 후위표현법을 계산하기 

 

• 중위표현법을 후위표현법으로 나타낼 때는 스택을 이용하는데 stack에다가는 연산자를 result에는 피연산자를 넣어가면서 구할 수 있다. stack에서 나중에 들어간 것이 먼저 나오므로 만약 먼저 들어간 것 중에 나중에 들어간 것보다 우선순위가 같거나 높은 것이 있다면 안된다. (연산자의 우선순위가 같으면 연산 방향의 우선순위를 고려하므로 나중에 들어간 것보다 먼저 들어간 것의 우선순위가 같아도 안됨)

예를 들어 연산자 우선순위는 [1,1,2,2]이고  '90*2+1 -5*2/3' 을 왼쪽부터 연산할 때 후위표현법으로 바꾸면

stack = [], result = [90]

stack = [*], result = [90]

stack = [*], result = [90,2] --> stack = [+], result = [90,2,*] 

stack = [+], result = [90,2,*,1] --> stack = [-],result = [90,2,*,1,+]

stack = [-], result = [90,2,*,1,+,5]

stack = [-], result = [90,2,*,1,+,5] --> stack = [-,*], result = [90,2,*,1,+,5]

stack = [-,*], result = [90,2,*,1,+,5,2]

stack = [-,*], result = [90,2,*,1,+,5,2] -> stack = [-,/], result = [90,2,*,1,+,5,2,*]

stack = [-,/], result = [90,2,*,1,+,5,2,*,3]

stack = [], result = [90,2,*,1,+,5,2,*,3,/,-] 으로 나타낼 수 있다. 

• 만약 괄호() 가 포함되어 있으면 '('의 연산자 우선순위를 제일 낮게 rank에 추가하고, '(' 은 무조건 스택에 넣고 ')'가 나오기 까지 위 과정을 반복하다 ')'가 나오면 '(' 와 ')' 사이에 있는 것들을 다 pop() 해서 result에다가 옮긴다. () 
• 또한 후위표현법을 계산하는 과정은 왼쪽부터 읽어 피연산자를 stack에 넣고 연산자를 만나면 stack에서 pop을 2번해서 둘이 연산하여 다시 스택에 넣고 이를 반복하면된다. .  

예를 들어 후위표현법으로 나타낸 수식 [90,2,*,1,+,5,2,*,3,/,-] 가 있을 때,

90을 스택에 넣음: stack = [90] 

2 스택에 넣음: stack = [90,2]

연산자(*)를 만났으므로 스택에서 두 개를 꺼내 연산하고 다시 스택에 넣는다. : stack = [180]

1 스택에 넣음 : stack = [180,1]     

연산자(+)를 만났으므로 스택에서 두개 꺼내 연산하고 다시 스택에 넣음 stack = [181] 

5 스택에 넣음 : stack = [181,5]

2 스택에 넣음 : stack =[181,5,2]

연산자(*)를 만났으므로 스택에서 두개 꺼내 연산하고 다시 스택에 넣음 stack = [181,10]

3 스택에 넣음 : stack = [181,10,3]

연산자(/)를 만났으므로 스택에서 두개 꺼내 연산하고 다시 스택에 넣음 stack = [181,3]

연산자(*)를 만났으므로 스택에서 두개 꺼내 연산하고 다시 스택에 넣음 stack = [178]

 

아래 작성한 코드는 중위표현법을 후위표현법으로, 후위표현법을 계산하는 함수를 나타낸다. rank는 우선순위를 의미한다. (괄호의 우선순위를 제일 작게 둔 것은 '('를 스택에 삽입했을 때 ')'를 만나기 전까지 어떤 경우에도 '('를 스택 밖으로 빠져나가지 않게 하기 위함이다.) 

rank = {
    '(' : 1,
    '+' : 2,
    '-' : 2,
    '*' : 3,
    '/' : 3
}

def solve1(prefix,rank): # 중위표현법을 왼쪽부터 읽을 때 후위표현법으로 바꾸는 함수
    stack = []
    result = []
    for c in prefix:
        if c == '(':
            stack.append(c)
        elif c in "+-*/":
            while stack and rank[stack[-1]] >= rank[c]:
                result.append(stack.pop())
            stack.append(c)
        elif c == ')':
            while True:
                tmp = stack.pop()
                if tmp == '(':
                    break
                result.append(tmp)
        else:
            result.append(c)
    while stack:
        result.append(stack.pop())
    return result

def solve2(postfix): # 후위표현법을 계산하는 함수
    stack = []
    for c in postfix:
        if c not in "+-*/":
            stack.append(int(c))
        elif c == '+':
            n1 = stack.pop()
            n2 = stack.pop()
            stack.append(n1+n2)
        elif c == '-':
            n1 = stack.pop()
            n2 = stack.pop()
            stack.append(n2-n1)
        elif c == '*':
            n1 = stack.pop()
            n2 = stack.pop()
            stack.append(n1*n2)
        elif c == '/':
            n1 = stack.pop()
            n2 = stack.pop()
            stack.append(n2/n1)
    return stack.pop()

이때 문제에선 연산을 뒤에서부터 하고 연산 우선순위가 다르다고 의미없는 0이 있을 수 있다는 점이 다르다. 또한 연산자에 괄호가 들어있지 않다. 이 점을 고려하여 위에서 위에서 구현한 코드를 조금 바꾸어 보자.

1. 먼저 연산 우선순위를 입력으로 주므로 rank의 각 key의 value를 넣어주었다.

rank = {}
inp = list(map(int,input().split()))
rank['+'],rank['-'],rank['*'],rank['/'] = inp[0],inp[1],inp[2],inp[3]

 

2. 의미없는 0을 없애기 위해 infix를 입력 받으면 연산자를 공백으로 replace하고 공백을 기준으로 split하여 숫자만 있는 num_list, 연산자만 있는 oper_list를 만들었다. 그리고 num_list와 oper_list를 서로 합쳐 의미없는 0을 없앤 inflix 를 만들었다.  

infix = input()
num_list = infix.replace('+',' ').replace('-',' ').replace('*',' ').replace('/',' ')
num_list = num_list.split()
num_list = [i.lstrip("0") for i in num_list]
oper_list = [i for i in infix if i in '+-*/']
print(num_list,oper_list)

infix = []
for i in range(len(oper_list)):
    infix.append(num_list[i])
    infix.append(oper_list[i])
infix.append(num_list[-1])

3. 오른쪽부터 연산할 때 바뀌는 점들을 고려해보자.

 

아까와 달라진 점은 후위표현법으로 나타낼 때 prefix를 오른쪽에서부터 읽는다는 점 말고는 다른 점이없다. 즉 solve1 함수의 매개변수로 prefix[ : : -1] 로 주면 오른쪽에서 읽은 후위표현법을 나타낼 수 있다. 후위표현법이 정해지면 solve2는 단순히 후위표현법을 따라 계산만하므로 동일하다. 따라서 다음과 같이 1,2,3을 종합해 코드를 작성해 제출했다. 

슬프게도 틀렸다. 알고리즘이 틀리지 않다고 생각했고 문제를 다시 천천히 읽어봤다. 

 

"C++에서 나눗셈은 나누어지는 수가 양수면 나머지가 0 이상, 음수면 나머지가 0 이하로 처리하여 나오는 몫을 계산한다. 예를 들어, 3 / 2 = 1, (−3) / 2 = −1, 3 / (−2) = −1, (−3) / (−2) = 1로 계산된다." 

혹시 파이썬과 C++의 몫 체계가 다른가 싶었는데 파이썬은 음의 나머지를 고려하지 않는다는 점에서 파이썬에서 (-3)//2 = -2 이고, (-3)//(-2) = 1 이고, 3//(-2) = -2 로 계산된다. 즉 이 부분을 다음과 같이 수정했다. 

        elif c == '/':
            n1 = stack.pop()
            n2 = stack.pop()
            if n1*n2 < 0:
                stack.append(-1* (abs(n2)//abs(n1)))
            else: 
                stack.append(n2//n1)

이렇게 제출했을 때 거의 100%까지 가서 IndexError가 발생했다. 어디서 IndexError가 발생한 것일까 고민하다 정말 못찾겠어서 이 문제는 여기서 마무리한다. 혹시 풀이에 오류가 있다면 댓글로 남겨주길 바란다. 

---

(추가) 댓글로 HeeJaYaa 님이 입력으로 0+0 일때 Index Error가 발생함을 지적해주었다. 의미없는 0을 제거해주는 부분에서 lstrip('0')을 사용하니 000...0 인 경우에 0이 되는 것이아닌 아예 없애버리는 문제가 있다. 이때는 다 없애버리는 것이 아닌 0 하나만 남겨두어야 한다. 이는 아래와 같이 해결할 수 있다. 

# infix는 중위표현법으로 나타낸 수식으로 입력받아서 의미없는 0을 제거한다.
num = "123456789"
infix = input()
num_list = infix.replace('+',' ').replace('-',' ').replace('*',' ').replace('/',' ')
num_list = num_list.split()
num_list = [i.lstrip("0") for i in num_list]
# 숫자가 0인 경우 num_list에서 '' 으로 되어있어 0으로 바꿔준다.
for i in range(len(num_list)): 
    if num_list[i] == '':
        num_list[i] = '0' 
oper_list = [i for i in infix if i in '+-*/']
infix = []
for i in range(len(oper_list)):
    infix.append(num_list[i])
    infix.append(oper_list[i])
infix.append(num_list[-1])

 

작성코드(Python3):

 

고생끝에 맞춰서 그런지 뿌듯하다. 앞으로 이런경우에 코너케이스를 잘 따져봐야겠다. 

def solve1(prefix,rank): # 중위표현법을 왼쪽부터 읽을 때 후위표현법으로 바꾸는 함수
    stack = []
    result = []
    for c in prefix:
        if c not in "+-*/":
            result.append(c)
        elif c in "+-*/":
            while stack and rank[stack[-1]] >= rank[c]:
                result.append(stack.pop())
            stack.append(c)
    while stack:
        result.append(stack.pop())
    return result

def solve2(postfix): # 후위표현법을 계산하는 함수
    stack = []
    for c in postfix:
        if c not in "+-*/":
            stack.append(int(c))
        elif c == '+':
            n1 = stack.pop()
            n2 = stack.pop()
            stack.append(n1+n2)
        elif c == '-':
            n1 = stack.pop()
            n2 = stack.pop()
            stack.append(n2-n1)
        elif c == '*':
            n1 = stack.pop()
            n2 = stack.pop()
            stack.append(n1*n2)
        elif c == '/':
            n1 = stack.pop()
            n2 = stack.pop()
            if n1*n2 < 0:
                stack.append(-1* (abs(n2)//abs(n1)))
            else:
                stack.append(n2//n1)
    return stack.pop()
# rank는 +,-,*,/ 의 우선순위를 담은 dict
rank = {'(':0}
inp = list(map(int,input().split()))
rank['+'],rank['-'],rank['*'],rank['/'] = inp[0],inp[1],inp[2],inp[3]

# infix는 중위표현법으로 나타낸 수식으로 입력받아서 의미없는 0을 제거한다.
infix = input()
num_list = infix.replace('+',' ').replace('-',' ').replace('*',' ').replace('/',' ')
num_list = num_list.split()
num_list = [i.lstrip("0") for i in num_list]
oper_list = [i for i in infix if i in '+-*/']
infix = []
for i in range(len(oper_list)):
    infix.append(num_list[i])
    infix.append(oper_list[i])
infix.append(num_list[-1])

# 오른쪽부터 읽으므로 infix 대신 이를 뒤집은 infix[::-1]을 solve1에 넣음
postfix = solve1(infix[::-1],rank)
print(solve2(postfix))