✅ stack

문제

링크

풀이

1. 문제 접근

괄호의 존재 유무에 따라, 또 연산자 우선순위(*, / 가 +, - 보다 먼저)에 따라 연산자 순서가 달라지는 문제다.

2. 자료구조 선택과 그 이유

위에서 말한 이유로 인해 stack에 우선순위가 낮은 연산자들을 담아 놨다가 우선순위가 높은 연산자를 출력한 후 그 다음 꺼내와야 한다.

3. 문제 해결 로직 (풀이법)

• 피연산자일 경우 (A ~ Z) : 곧바로 정답 vector에 추가
• 연산자일 경우 (+, -, *, /, "(", ")")
  • +, -
    1. stack안에 자신보다 우선순위가 높은 연산자(*, /)가 있으면 안되므로 전부 pop 및 정답 vector에 추가
       괄호는 +, - 보다 우선순위가 높긴 하지만 현재 +, - 이후에 나올 연산자들도 모았다가 처리해야 하므로 열린 괄호가 나오기 전까지만 pop 및 정답 vector에 추가해줌.
    2. stack에 push
  • *, /
    1. 자신과 우선순위가 같을 경우에는 나온 순서에 따르므로 stack에서 자신과 우선순위가 같은 연산자(, /)를 pop 및 정답 vector에 추가
       +, - 와 다르게 , / 가 들어간 연산은 괄호처리를 해주지 않으므로 괄호는 신경쓰지 않아도 됨
    2. stack에 push
  • "("
    1. stack에 push
  • ")"
    1. "(" 가 나올 때 까지 pop 및 정답 vector에 추가

의사코드

// stack : 연산자를 담아놓을 스택, str : 주어진 표기식

cin >> str

for(i : str인덱스){
	if(str[i] == A ~ Z){
    	vector.push_back(str[i])
    }
	if(str[i] == + or -){
    	while(!stack.empty and str[i]!='('){
        	vector.push_back(stack.top)
            stack.pop
        }
    	vector.push_back(str[i])
    }
    if(str[i] == * or /){
    	while(!stack.empty and (stack.top == * or stack.top == /)){
        	vector.push_back(stack.top)
            stack.pop
        }
        vector.push_back(str[i])
    }
    if(str[i] == '('){
    	vector.push_back(str[i])
    }
    if(str[i] == ')'){
    	while(!stack.empty and stack.top != '('){
        	vector.push_back(stack.top)
            stack.pop
        }
        stack.pop // '(' 제거
    }
}

while(!stack.empty){ // 마지막에 남아있는 연산자 제거
	vector.push_back(stack.top)
    stack.pop
}

print(vector) // 후위 표기식 출력

4. 시간 복잡도 분석

O(N^2)

5. 문제에서 중요한 부분

이전 후위표기식을 계산하는 문제에서도 stack을 사용했기 때문에 stack을 떠올리는 것은 어렵지 않았다.
하지만 이전 문제에서는 피연산자를 stack에 담아 활용했지만 이번 문제는 연산자의 순서가 바뀌므로 연산자를 stack에 담아 활용해야 한다는 점과
연산자의 종류에 따라 stack에서 pop해줄때 조건들을 떠올리기 쉽지 않았다.