[Algorithm] 후위표기식 만들기 (스택) (Feat. isdecimal())

중위표기식이 입력되면 후위표기식으로 변환하는 프로그램을 작성하세요.
중위표기식은 우리가 흔히 쓰은 표현식입니다. 즉 3+5 와 같이 연산자가 피연산자 사이에 있으면 중위표기식입니다. 후위표기식은 35+ 와 같이 연산자가 피연산자 뒤에 있는 표기식입니다. 예를 들어 중위표기식이 3+52 를 후위표기식으로 표현하면 352+ 로 표현됩니다. 만약 다음과 같이 연산 최우선인 괄호가 표현된 식이라면 (3+5)2 이면 35+2 로 바꾸어야 합니다.

<내 답안>

a = input()
stack = []
result = ''
for i in range(len(a)):
    if a[i] == '+' or a[i] == '-':
        if len(stack) != 0 and (stack[-1] == '+' or stack[-1] == '-' or stack[-1] == '*' or stack[-1] == '/'):
            result = result + stack.pop()
            stack.append(a[i])
        else:
            stack.append(a[i])

    elif a[i] == '*' or a[i] == '/':
        if len(stack) != 0 and (stack[-1] == '*' or stack[-1] == '/'):
            result = result + stack.pop()
            stack.append(a[i])
        else:
            stack.append(a[i])

    elif a[i] == '(' or a[i] == ')':
        if a[i] == '(':
            stack.append('(')
        elif a[i] == ')':
            m = stack.pop()
            while m != '(':
                result = result + m
                m = stack.pop()

    else:
        result = result + a[i]

if len(stack) != 0:
    for i in range(1, len(stack)+1):
        result = result + stack[-i]

print(result)

내 답안이 틀린 이유를 알았다.
stack에서 top을 한 번만 꺼내는 것이 아닌 '(' 만나기 전이나, 스택이 비어있기 전까지 전부 꺼내야 했다. 따라서 if문이 아니라 반복문을 써야했다.
if를 while로만 고치면 된다.

a = input()
stack = []
result = ''
for i in range(len(a)):
    if a[i] == '+' or a[i] == '-':
        while len(stack) != 0 and (stack[-1] == '+' or stack[-1] == '-' or stack[-1] == '*' or stack[-1] == '/'):
            result = result + stack.pop()
        stack.append(a[i])

    elif a[i] == '*' or a[i] == '/':
        while len(stack) != 0 and (stack[-1] == '*' or stack[-1] == '/'):
            result = result + stack.pop()
        stack.append(a[i])

    elif a[i] == '(' or a[i] == ')':
        if a[i] == '(':
            stack.append('(')
        elif a[i] == ')':
            m = stack.pop()
            while m != '(':
                result = result + m
                m = stack.pop()

    else:
        result = result + a[i]

if len(stack) != 0:
    for i in range(1, len(stack)+1):
        result = result + stack[-i]

print(result)

해설 들으면서 isdecimal()이라는 함수를 알았다.
10진수이면 true, 아니면 false라고 한다. 모범답안에서는 이 함수로 피연산자를 구분할 때 사용했다.

💡 isdecimal() : 해당 문자열이 0~9까지의 수로 이루어져있는지 검사 (= int로 바로 변환할 수 있는 수인지 검사)

<모범답안>

a = input()
stack = []
res = ''
for x in a:
    if x.isdecimal():  # 피연산자
        res += x
    else:
        if x == '(':
            stack.append(x)
        elif x == '*' or x == '/':
            while stack and (stack[-1] == '*' or stack[-1] == '/'):
                res += stack.pop()
            stack.append(x)
        elif x == '+' or x == '-':
            while stack and stack[-1] != '(':
                res += stack.pop()
            stack.append(x)
        elif x == ')':
            while stack and stack[-1] != '(':
                res += stack.pop()
            stack.pop()
while stack:
    res += stack.pop()
print(res)