파이썬 알고리즘 034 | 후위표기식 만들기 ***

34. 후위표기식 만들기

중위표기식이 입력되면 후위표기식으로 변환하는 프로그램을 작성하세요.
중위표기식은 우리가 흔히 쓰은 표현식입니다. 즉 3+5 와 같이 연산자가 피연산자 사이에 있으면 중위표기식입니다.
후위표기식은 35+ 와 같이 연산자가 피연산자 뒤에 있는 표기식입니다.
예를 들어 중위표기식이 3+52 를 후위표기식으로 표현하면 352+ 로 표현됩니다.
만약 다음과 같이 연산 최우선인 괄호가 표현된 식이라면
(3+5)2 이면 35+2 로 바꾸어야 합니다.
▣ 입력설명
첫 줄에 중위표기식이 주어진다. 길이는 100을 넘지 않는다.
식은 1~9의 숫자와 +, -, , /, (, ) 연산자로만 이루어진다.
▣ 출력설명
후위표기식을 출력한다.
▣ 입력예제 1
3+52/(7-2)
▣ 출력예제 1
35272-/+
▣ 입력예제 2
3(5+2)-9
▣ 출력예제 2
352+*9-

<내 풀이>

stack=[]
k=[]
# * 나 () 같은 우선 계산 되어야 할 애들은 그 두개의 수 바로 뒤에
n=input()
n=list(map(str,n))

for i in range(len(n)) : 
    if 
    elif n[i].isdecimal():
        stack.append(n[i])
        if n[i-1]=='*' or n[i-1]=='/':
            stack.append(n[i-1])

    elif n[i].isdecimal()==False and n[i] != '*' and n[i] !='/' :
        k.append(n[i])
print(stack)
print(k)
#print(stack)스택 안에 숫자만 추출해놓음
#마지막에 만난 애가 처음 스택으로 들어감
#근데 * 이랑 () 안에 있는 부호는 숫자 바로 다른'''

=> 나름 열심히 도전해봤는데 자꾸 예외 사항들이 생기고 빈틈이 너무 많아서 실패
=> 우선 순위가 괄호 , & / , 나머지 부호들 인것을 알겠는데
괄호안의 부호는 어떻게 덧붙여야 하는지, 나머지 '','/' 는 어떤 기준으로 덧붙여야 하는지 계속 고민해봤는데 찾지 못했다 기준을
=======> 부호들을 스택에 넣어주고 입력되는 애보다 스택 안에 우선순위가 높은 애가 있으면 걔를 pop해주고 숫자들 누적해준데에 넣어준다

n=input()
res=''
stack=[]

for i in range(len(n)) : 
    if n[i].isdecimal() : 
        res+=n[i]
    else : 
        stack.append(n[i])
        if n[i] 
        ................ㅠㅠ

• 설명을 듣고 구현을 해보려고 했는데 아직 어렵다

<풀이>

• 먼저 숫자를 만나면 다른 곳에 누적을 해준다
• 연산자들을 만나면 stack에 넣어준다
• 근데 연산자들 stack에 넣어주다가 들어와있는 연산자 중에 자기보다 우선순위 높은 연산자가 있으면 걔를 pop해주고 숫자들 누적해준 데 더해준다
  -'(' 은 ')' 나오기 전까지 안에 있는 연산자 계속 받아주다가 ')' 나오면 그제서야 pop해주어야 한다. 괄호 안의 게 최우선이니깐 괄호 안의 연산자들은 save해준다

n=input()
res=''
stack=[]

for x in n : 
    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() #괄호 안 연산자들을 res에 더해준 것이다
            stack.append(x)
        elif x==')' : 
            while stack and stack[-1]!='(' : 
                res+=stack.pop() #여는 괄호 사이에 있는 애들을 res에 더해줌
            stack.pop() #여는 괄호 pop
while stack :
    res+=stack.pop()
print(res)

<반성점>

• 너무 문제 해결력이 부족하다는 것을 느끼는 요즘이다
  대신 한번 배운 개념들은 잊지 말고 계속 복습하자

<배운 점>

• 후위 표기식, 연산자 사이에 우선순위 정해서 스택에서 pop이랑 append를 유연하게 해주면 된다

• 모든 경우의 수를 고려해주기,
  ====> 나보다 높은 애들은 다 숫자로 쫓아내야지, 하는 마인드로

• ()가 최우선 순위이고 따라서 그 안에 있는 애들은 먼저 계산되어야 한다
  따라서 (가 나오면 무조건 stack에다가 넣어주고 뒤에 애들을 받는다

• ,/ 같은 경우는 얘네 오기 전 앞에 ,/ (*,/는 왼쪽에 있을 수록 우선순위가 높아지므로) 있으면 얘네 pop시켜서 숫자들에게 보내버린다

• +,- 는 최약체다. stack에 무언가 있는 이상 얘네보다 무조건 센 애들이므로
  다 보내버려야 한다. 다만 다 보내버리면은 안되구 일단 괄호 안에 있는 애들 우선 보내야 하니깐 열린 괄호 전에 존재하는 애들만 보내버린다 (괄호 안에 있는 애들 res에 넣어주는 과정')

• 그리고 닫힌 괄호 ) 가 나오면 괄호는 어디에도 포함되어있으면 안될거고
  앞에 +,- 등이 다 괄호안에 있는 애들 빼가고 남은 열린 괄호 하나를 pop시켜버리는 동작만 한다. 그럼 괄호는 빠지게 된다

• 그리고 stack에 남아있는 애들은 이제 다 res로 보내주면 된다