파이썬 알고리즘 154번 | [백준 1918번] 후위표기식(3) - 스택

154. 후위표기식(3)

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

<다른 분의 풀이>

출처 : https://pannchat.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%B0%B1%EC%A4%80-%ED%9B%84%EC%9C%84%ED%91%9C%EA%B8%B0%EC%8B%9D-python

strn = list(input())
stack=[]
res=''
for s in strn:
    if s.isalpha():
        res+=s
    else:
        if s == '(':
            stack.append(s)
        elif s == '*' or s == '/':
            while stack and (stack[-1] == '*' or stack[-1] =='/'):
                res += stack.pop()
            stack.append(s)
        elif s == '+' or s == '-':
            while stack and stack[-1] != '(':
                res+= stack.pop()
            stack.append(s)
        elif s == ')':
            while stack and stack[-1] != '(':
                res += stack.pop()
            stack.pop()
while stack :
    res+=stack.pop()
print(res)

<내 틀렸던 풀이, 문제점>

import sys
inp=list(sys.stdin.readline().rstrip())

seq=[")", "+", "-", "*", "/", "("]
op=[]
res=[]

for i in range(len(inp)) :
    if inp[i].isalpha():
        res.append(inp[i])
    else :
        if op and seq.index(op[-1]) >= seq.index(inp[i]):
            #내가 우선순위 낮으면 op안에 있는 애들 다 res에 붙여
            for j in range(0,len(op)) :
                if op[-1]!="(" and op[-1]!=")":
                    res.append(op.pop()) 
        op.append(inp[i])

while op :
    res.append(op.pop())

for i in res:
    if i!="(" and i!=")" :
        print(i,end="")

• 이 지점에서 틀렸다고 뜬다,, 안되는 테케를 찾고싶은데 ㅠㅠ 뭘까

디버깅 발견

• 괄호 ) 를 만나면 ( 만날 때까지로 끊어주고, -와 + 그리고 * 와 / 를 같은 우선순위로 취급해야해

import sys
inp=list(sys.stdin.readline().rstrip())

seq=[")", 0,0,"+", "-",0,0, "*", "/", 0,0,"("]
op=[]
res=[]

for i in range(len(inp)) :
    # print(inp[i])
    # print(op)

    if inp[i].isalpha():
        res.append(inp[i])
    else :
        #if op and (seq.index(op[-1]) > seq.index(inp[i]) and seq.index(op[-1]) - seq.index(inp[i])>1):
        #if op and seq.index(op[-1]) >= seq.index(inp[i]):
        if inp[i]==")" :
            # print("hey", op)
            while op and op[-1]!="(" :
                res.append(op.pop())
            op.pop()
        elif op and ((seq.index(op[-1]) - seq.index(inp[i])) >=1 or (seq.index(op[-1]) - seq.index(inp[i]))==-1):
            #print(seq.index(op[-1]), seq.index(inp[i]), (seq.index(op[-1]) - seq.index(inp[i])))
            #내가 우선순위 낮으면 op안에 있는 애들 다 res에 붙여
            for j in range(0,len(op)) :
                if op[-1]!="(" and op[-1]!=")":
                    res.append(op.pop()) 
        if inp[i]!=")" :
            op.append(inp[i])

while op :
    res.append(op.pop())

for i in res:
    if i!="(" and i!=")" :
        print(i,end="")

<반성 점>

<배운 점>