백준 1918- 후위 표기식(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

stack을 이용해 푸는 문제였습니다.

중위 표기식이 주어졌을 때, 후위 표기식으로 고치는 문제입니다.

후위 표기식의 특징은 연산자와 문자가 섞여있는 것이 아닌, 문자가 먼저 나오고 연산자가 나온다는 점입니다.

연산자 또한, 우선 순위가 있음으로 이에 따라 출력해주면 됩니다.

 

• 풀이 방법
  • 피연산자는 A ~ Z는 입력 즉시 출력해준다
  • +, - , * , / 가 입력되었을 경우, stack의 top의 연산자보다 우선 순위가 낮지 않을 경우, stack의 top을 출력하고 pop 해준다.
  • ( 가 입력 되었을 경우, stack에 넣어주고, )가 입력 되었을 경우 (가 나올 때까지 stack의 top을 출력하고 pop 해준다.
  • 문자열을 전부 확인했음에도 stack에 데이터가 남아있다면 빌 때까지 top을 출력하고 pop 해줍니다.

 

(A + ( B * C )) - (D / E) 를 통해 확인해보겠습니다.

2 , 5번 과정에서 ')'가 입력 되었음으로 '('가 나올때까지 출력합니다.

3번 과정에서 '-'가 입력 되었음으로 '+'를 출력해줍니다.

6번 과정에서 문자열 확인은 끝났지만, stack에 값은 남아있음으로 남은 값을 전부 출력해줍니다.

-> 해당과정을 통해 값이 정확히 나옴을 확인할 수 있습니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <stack>

using namespace std;

string formula;
stack<char> save;

void solve() {
	for (int i = 0; i < formula.size(); i++) {
		if (formula[i] >= 'A' && formula[i] <= 'Z') {
			cout << formula[i];
		}
		else {
			if (formula[i] == '(') save.push(formula[i]);
			else if (formula[i] == '*' || formula[i] == '/') {
				while (!save.empty() && (save.top() == '*' || save.top() == '/')) {
					cout << save.top();
					save.pop();
				}
				save.push(formula[i]);
			}
			else if (formula[i] == '+' || formula[i] == '-') {
				while (!save.empty() && save.top() != '(') {
					cout << save.top();
					save.pop();
				}
				save.push(formula[i]);
			}
			else {
				while (!save.empty() && save.top() != '(') {
					cout << save.top();
					save.pop();
				}
				save.pop();
			}
		}
	}
	while (!save.empty()) {
		cout << save.top();
		save.pop();
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> formula;
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요