[Section05] Python 알고리즘 문제풀이 03~04

Q3. 후위표기식 만들기 : 입력된 중위표기식을 후위표기식으로 변환

입력 : 중위표기식

출력 : 후위표기식

 

[내가 쓴 코드]

#어디에 내놓아도 부끄러운 내 코드,,,
sample = {'(': 0, ')' : 0, '*' : 1, '/' : 1, '+' : 2, '-' : 2}

a = list(input())
result = list()
operator = list()

for x in a :
    if x == '*' or x == '/' or x == '+' or x == '-' :
        if len(operator) == 0 :
            operator.append(x)
        elif sample[operator[len(operator) - 1]] >= sample[x] :
            print(operator[len(operator) - 2], x)
            print("!", sample[operator[len(operator) - 2]], sample[x])
            temp = operator.pop()
    else :
        result.append(x)
        
result.append(operator.pop())

print(operator, result)

 

[풀이 코드]

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 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)

 

연산자의 우선순위를 지정하기 위해 dictionary를 사용함

stack 하나로 풀 수 있었다니...

 

---

Q4. 후위식 연산 : 입력된 후위표기식을 계산하여 출력

입력 : 후위표기식

출력 : 계산결과

 

[내가 쓴 코드]

a = list(str(input()))
b = list()

#연산자일 경우 stack에 있는 숫자를 빼서 계산 후 다시 저장
for x in a :
    if x == '+' :
        operand1 = b.pop()
        operand2 = b.pop()
        b.append(operand2 + operand1)
    elif x == '-' :
        operand1 = b.pop()
        operand2 = b.pop()
        b.append(operand2 - operand1)
    elif x == '/' :
        operand1 = b.pop()
        operand2 = b.pop()
        b.append(operand2 / operand1)
    elif x == '*' :
        operand1 = b.pop()
        operand2 = b.pop()
        b.append(operand2 * operand1)
    else :
        b.append(int(x))
    
print(*b)  #print(b[0])

 

[풀이 코드]

a = input()
stack = []

for x in a :
    if x.isdecimal() :
        stack.append(int(x))
    else :
        if x == '+' :
            n1 = stack.pop()
            n2 = stack.pop()
            staca,append(n2 + n1)
        elif x == '-' :
            n1 = stack.pop()
            n2 = stack.pop()
            staca,append(n2 - n1)
        elif x == '*' :
            n1 = stack.pop()
            n2 = stack.pop()
            staca,append(n2 * n1)
        elif x == '/' :
            n1 = stack.pop()
            n2 = stack.pop()
            staca,append(n2 / n1)
            
print(stack[0])

 

 

a list, b list 이렇게 생성하는 대신 그때 그때 입력받고 싶었는데 방법을 찾지 못하였음

3번보다 훨씬 쉬웠다...