스택

문제 1

가장 큰 수

선생님은 현수에게 숫자 하나를 주고, 해당 숫자의 자릿수들 중 m개의 숫자를 제거하 여 가장 큰 수를 만들라고 했습니다. 여러분이 현수를 도와주세요.(단 숫자의 순서는 유지해야 합니다)
만약 5276823 이 주어지고 3개의 자릿수를 제거한다면
7823이 가장 큰 숫자가 됩니다.

▣ 입력설명

첫째 줄에 숫자(길이는 1000을 넘지 않습니다)와 제가해야할 자릿수의 개수가 주어집니다.

▣ 출력설명
가장 큰 수를 출력합니다.

▣ 입력예제 1 5276823 3
▣ 출력예제 1 7823
▣ 입력예제 2 9977252641 5
▣ 출력예제 2 99776

num , m = map(int,input().split())
num = list(map(int,str(num)))

stack = []
for x in num:
    while stack and m > 0 and stack[-1] < x :# stack 에 먼가 있으면 돌아가고 빈 리스트면 멈춤
        stack.pop()  #앞에와 비교해서 작으면 지움
        m-=1 # 횟수를 감소
    stack.append(x)
if m!=0: # more delete
    stack = stack[:-m] # 내림차순 정렬이라 남은 m만큼 날려버림

res = ''.join(map(str,stack))
print(res)

문제2

후위표기식 만들기

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

# 접근

# 순서가 있는 연산자를 스택 집합안에 만약 연산처리가 더 빠른게 온다면 그대로 / 느린게 온다면 pop을 해서 숫자 집합으로  ( 아직 적용안된 연산자 개념)
# (  언제나 append--> 닫는괄호 만나기 전까지 적용이 아닌니까)
# 숫자는 최종 출력 값에 쌓는다


a= input()

stack =[]
res =''

for x in a:
    if x.isdecimal(): ##number ==> accumulate
        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)

           

문제3

후위식 계산

후위연산식이 주어지면 연산한 결과를 출력하는 프로그램을 작성하세요.
만약 3(5+2)-9 을 후위연산식으로 표현하면 352+9- 로 표현되며 그 결과는 21입니다.
▣ 입력설명
첫 줄에 후위연산식이 주어집니다. 연산식의 길이는 50을 넘지 않습니다. 식은 1~9의 숫자와 +, -, *, /, (, ) 연산자로만 이루어진다.
▣ 출력설명
연산한 결과를 출력합니다.

▣ 입력예제 1 352+*9-
▣ 출력예제 1 12

# 연산자를 만나면 앞의 두숫자와 연산 + 연산한값을 다시 푸시 
# 숫자는 무조건 stack 푸시
## 정답

a = input()
stack = []

for x in a:
    if x.isdecimal():
        stack.append(int(x))
    elif x == '+':
        n1 = stack.pop()
        n2 = stack.pop()
        res = n2 +n1
        stack.append(res)
    elif x == '-':
        n1 = stack.pop()
        n2 = stack.pop()
        res = n2 - n1
        stack.append(res)
    elif x == '*':
        n1 = stack.pop()
        n2 = stack.pop()
        res = n2 * n1
        stack.append(res)
    elif x == '/':
        n1 = stack.pop()
        n2 = stack.pop()
        res = n2 / n1
        stack.append(res)

    print(stack)
print(stack[-1])