문제 출처 : SW Expert
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
www.swexpertacademy.com
Q. 더하기, 곱셈 연산으로 된 식이 주어졌을 때, 후위식으로 변환하여 계산하는 프로그램을 작성하시오.
문제에 대한 해결 방향은 문제에서 제시해줬어요. 후위식으로 변환한 다음 스택을 이용해서 문제를 해결하는 것이죠.
따라서 이 문제의 핵심은 후위식으로 변환하는 거라고 생각했습니다.
우선, 연산이 더하기, 곱셈 두 가지 뿐이라는 점에서 그렇게 까다로운 문제는 아닌 거 같아요.
케이스가 두 가지 밖에 나오지 않는 것이죠. 더하기, 곱하기.
먼저, 변환 과정에서 곱하기 연산을 만나면 (숫자1) * (숫자2) 이런 형태를 => (숫자1)(숫자2)*로 변환 해주면 됩니다.
적당히 반복문에서 인덱스를 조작해서 쉽게 해결할 수 있습니다.
그 다음, 더하기 연산은 우선순위가 가장 낮기 때문에 언제 더하기를 해줘도 상관이 없다고 생각했어요.
그래서 더하기 연산의 개수를 카운트해서 후위식 끝에 몰아서 넣어줬습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#include<iostream>
#include<string>
#include<vector>
using namespace std;
string s;
int num[10000];
int top = 0;
int main() {
int T = 10;
int idx = 0;
while (idx++ < T) {
int n;
cin >> n;
cin >> s;
string postfix;
int plus_num = 0;
for (int i = 0; i < n; i++) {
char c = s[i];
if (c >= '0' && c <= '9') {
postfix += c;
}
else if (c == '+') {
plus_num++;
}
else if (c == '*') {
postfix += s[++i];
postfix += '*';
}
}
for (int i = 0; i < plus_num; i++) { // 뒤에 몰아넣기
postfix += '+';
}
for (int i = 0; i < n; i++) {
char c = postfix[i];
if (c >= '0' && c <= '9') {
num[top++] = c - '0';
}
else if (c == '+') {
int a = num[--top];
int b = num[--top];
int cal = a + b;
num[top++] = cal;
}
else if (c == '*') {
int a = num[--top];
int b = num[--top];
int cal = a * b;
num[top++] = cal;
}
}
cout << "#" << idx << " " << num[0] << endl;
top = 0;
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter
|
|
의견이 있으시거나 수정해야할 부분이 있으면 편하게 공유 부탁드립니다!
'전체 > 알고리즘 문제풀이' 카테고리의 다른 글
| 백준 15684. 사다리 조작 (0) | 2019.04.11 |
|---|---|
| SW Expert 1232. [S/W 문제해결 기본] 9일차 - 사칙연산(D4) (0) | 2019.04.04 |
| SW Expert 1227. [S/W 문제해결 기본] 7일차 - 미로2 (D4) (0) | 2019.04.04 |
| 후위연산식으로 변환 (0) | 2019.04.02 |
| SW Expert 1224. [S/W 문제해결 기본] 6일차 - 계산기3(D4) (0) | 2019.04.02 |