๐ฃ ๋ฌธ์ ์ดํด
ํ์ ํ๊ธฐ๋ฒ(postfix)์ ์ฐ์ฐ์๊ฐ ํผ์ฐ์ฐ์ ๋ค์ ์์นํ๋ ๋ฐฉ๋ฒ์ด๋ค.
์๋ฅผ ๋ค์ด a+b*c๋ฅผ ํ์ ํ๊ธฐ์์ผ๋ก ๋ฐ๊พธ๋ฉด abc*+๊ฐ ๋๋ค.
์ค์ ํ๊ธฐ์์ด ์ฃผ์ด์ก์ ๋ ํ์ ํ๊ธฐ์์ผ๋ก ๊ณ ์น๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ๋ค.
์คํ(Stack)์ ํ์ฉํ์ฌ ํ์ดํ๋ค.
๐ญ ํ์ด ๊ณผ์
C++ Stack ๋ผ์ด๋ธ๋ฌ๋ฆฌ๋ฅผ ์ฐธ์กฐํ์ฌ ์ค์ ํ๊ธฐ๋ฒ์ ๊ตฌํํ์๋ค.
์์ฑ ์ธ์ด: C++
#include <iostream>
#include <stack>
using namespace std;
int main() {
string expression = "";
stack<char> s1;
cin >> expression;
for (int i = 0; i < expression.length(); ++i) {
if (expression[i] >= 60) {
// ํผ์ฐ์ฐ์ ์ถ๋ ฅ(๋ชจ๋ ๋ฌธ์ ์ซ์๋ ASCII ์ฝ๋๋ก 60 ์ด์์)
cout << expression[i];
}else {
if (expression[i] == '*' || expression[i] == '/') {
if (!s1.empty()) {
if (s1.top() == '*' || s1.top() == '/') {
cout << s1.top();
s1.pop();
}
}
s1.push(expression[i]);
}else if (expression[i] == '+' || expression[i] == '-') {
if (s1.empty()) {
s1.push(expression[i]);
}else {
while (!s1.empty()) {
if (s1.top() == '(') break;
cout << s1.top();
s1.pop();
}
s1.push(expression[i]);
}
}else if (expression[i] == '(') {
s1.push(expression[i]);
}else if (expression[i] == ')') {
while (s1.top() != '(') {
cout << s1.top();
s1.pop();
}
s1.pop();
}else {
cout << "๋ญ๊ฐ ์๋ชป ์ฝ์ด์์!!!" << endl;
exit(1);
}
}
}
while (!s1.empty()) {
cout << s1.top();
s1.pop();
}
}
โ๏ธ "*" ๋๋ "/" ์ฐ์ฐ์์ ๊ฒฝ์ฐ
1) ์คํ์ด ๋น์ด์์ง ์๋ค๋ฉด, ์คํ์ top์ด "*"์ "/"์ธ ๊ฒฝ์ฐ ๋์ผํ ์ฐ์ ์์์ด๋ฏ๋ก pop ์ํจ๋ค.
2) ์๋ก ์ฝ์ด์จ ์ฐ์ฐ์๋ฅผ push ํ๋ค.
โ๏ธ "+" ๋๋ "-" ์ฐ์ฐ์์ ๊ฒฝ์ฐ
1) ์คํ์ด ๋น์ด์๋ค๋ฉด ๊ทธ๋ฅ push ํ๋ค.
2) ๋น์ด์์ง ์๋ค๋ฉด, ์คํ์ด ๋น์์ง๊ฑฐ๋ ์ฌ๋ ๊ดํธ("(")๋ฅผ ๋ง๋ ๋๊น์ง pop ํ๋ค. ๊ทธ ํ ์๋ก ์ฝ์ด์จ ์ฐ์ฐ์๋ฅผ push ํ๋ค.
โ๏ธ "(" ๋๋ ")"์ ๊ฒฝ์ฐ
1) "("์ ๊ฒฝ์ฐ ๋ฌด์กฐ๊ฑด push ํ๋ค.
2) ")"์ ๊ฒฝ์ฐ ์ฌ๋ ๊ดํธ("(")๋ฅผ ๋ง๋ ๋๊น์ง pop ํ๋ค. ์ดํ ์ฌ๋ ๊ดํธ ์ญ์ pop ํ๋ค.
๐ ๋ฐฐ์ด ์
์๋ฃ๊ตฌ์กฐ ์์ ์๊ฐ์ ์คํ์ ๋ฐฐ์ฐ๋ฉด์ ๊ณผ์ ๋ก ์ํํ๋ ์ค์ ํ๊ธฐ์ -> ํ์ ํ๊ธฐ์ ๋ณํ์ ๊ตฌํํ๋ ๋ด์ฉ์ด์๋ค.
์ญ์ ์ค๋๋ง์ ๋ณต์ตํ๋ฉฐ ๋ค์ ๋ด์ฉ์ ์๊ธฐํ ์ ์์ด ์ ์ตํ๋ค.
'Problem_Solving' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[2020 ์นด์นด์ค ์ธํด์ญ for Tech developers] ํคํจ๋ ๋๋ฅด๊ธฐ (0) | 2020.08.27 |
---|---|
[BOJ] ๋ฐฑ์ค 1935 ํ์ ํ๊ธฐ์2 / ์คํ(Stack) (0) | 2020.07.27 |
[BOJ] ๋ฐฑ์ค 10828 ์คํ / ์คํ(Stack) (0) | 2020.07.17 |
[2019 ์นด์นด์ค ๊ฐ๋ฐ์ ๊ฒจ์ธ ์ธํด์ญ] ๋ถ๋ ์ฌ์ฉ์ (0) | 2020.05.01 |
[2019 ์นด์นด์ค ๊ฐ๋ฐ์ ๊ฒจ์ธ ์ธํด์ญ] ํํ (0) | 2020.05.01 |