아직 골드 정도의 난이도는 스스로 풀이를 떠올리는데에 힘이 드는 것 같다.
다른 사람의 풀이를 참고했고 이 문제는 스택 자료구조를 사용해서 풀 수 있다.
주어진 문자열을 앞에서 부터 하나씩 체크하면서 answer
에 결과를 더해준다.
일반 알파벳일 경우 그냥 더해주고, 다른 연산자의 경우 규칙에 맞게 스택을 활용해 담아서 처리한다.
(
를 만나면 스택에 그냥 푸시한다.*
와 /
연산자의 경우 다른 연산자 보다 우선순위가 크므로 그냥 스택에 푸시해주면 되지만 이미 먼저 스택에 *
와 /
연산자가 담겨있는 경우 해당 연산자의 우선 순위가 높으므로 그 연산자만 미리 꺼내어 answer
에 더해준다.+
와 -
연산자는 연산자의 우선 순위가 낮으므로 스택에 담겨진 모든 연산자를 꺼내어 answer
에 더해준다.)
연산자의 경우 스택에 담겨있는 연산자들의 우선순위가 가장 높으므로(괄호에 둘러싸여 있어서) (
가 스택의 top일 때까지 answer
에 pop하여 더해준다.(
를 제거해야 해서 while
문 종료 후에 한 번더 pop 해준다.위의 규칙으로 JS와 C++를 사용해서 풀었다.
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();
class Stack {
constructor() {
this.stack = [];
}
push(value) {
this.stack.push(value);
}
pop() {
if (this.size() === 0) return -1;
return this.stack.pop();
}
top() {
return this.size() ? this.stack[this.size() - 1] : -1;
}
size() {
return this.stack.length;
}
empty() {
return this.size() === 0 ? 1 : 0;
}
}
const solution = (str) => {
const stack = new Stack();
let answer = '';
const alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
for (const ch of str) {
if (alphabet.includes(ch)) {
answer += ch;
} else if (ch === '(') {
stack.push('(');
} else if (ch === '*' || ch === '/') {
while (stack.top() === '*' || stack.top() === '/') answer += stack.pop();
stack.push(ch);
} else if (ch === '+' || ch === '-') {
while (!stack.empty() && stack.top() !== '(') answer += stack.pop();
stack.push(ch);
} else if (ch === ')') {
while (!stack.empty() && stack.top() !== '(') answer += stack.pop();
stack.pop();
}
}
while (!stack.empty()) answer += stack.pop();
return answer;
};
console.log(solution(input));
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
string str; cin >> str;
stack<char> S;
string answer = "";
for (auto &ch : str) {
if ('A' <= ch && ch <= 'Z') answer += ch;
else if (ch == '(') S.push(ch);
else if (ch == ')') {
while(!S.empty() && S.top() != '(') {
answer += S.top();
S.pop();
}
S.pop();
}
else if (ch == '*' || ch == '/') {
while(!S.empty() && (S.top() == '*' || S.top() == '/')) {
answer += S.top();
S.pop();
}
S.push(ch);
}
else if (ch == '+' || ch == '-') {
while(!S.empty() && S.top() != '(') {
answer += S.top();
S.pop();
}
S.push(ch);
}
}
while(!S.empty()) {
answer += S.top();
S.pop();
}
cout << answer << '\n';
return 0;
}