중위표기식이 입력되면 후위표기식으로 변환하는 프로그램을 작성하세요.
중위표기식은 우리가 흔히 쓰은 표현식입니다. 즉 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)