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

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

1918번: 후위 표기식

 

 

 

접근방식

 

1. 후위 표기식으로 변환하는 문제

2. 자료구조중 에서 스택을 사용하면 쉽게 구할 수 있다.

3. 연산자를 스택에 넣어놓으며 진행 

 

문제풀이 

1. 연산자는 스택에 있는 값과 값을 비교하며 진행

2. *,/ 이 나온 경우

스택에서 *,/ 가 나오면 스택에서 POP하고 결과에 추가

3. +,-가 나온 경우

스택에서 *,/,+,- 가 나오면 스택에서 POP하고 결과에 추가

4. )가 나온 경우

(가 나올때 까지 POP하고 결과에 추가

 

즉 연산자들의 우선 순위는 *,/ > +,- > ( 순 입니다.

 

아래는 정답 코드입니다.

#include <iostream>
#include <stack>
#include <string>
using namespace std;

string input;
string result;
stack <char> stk;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> input;

	for (int i = 0; i < input.size(); i++) {
		if (input[i] >= 'A' && input[i] <= 'Z')
			result += input[i];
		else {
			if (stk.empty())
				stk.push(input[i]);
			else {
				if (input[i] == '(')
					stk.push(input[i]);
				else if (input[i] == ')') {
					while (1) {
						char temp = stk.top();
						stk.pop();
						if (temp == '(')
							break;
						result += temp;
					}
				}
				else if (input[i] == '+' || input[i] == '-') {
					while (!stk.empty() && stk.top() != '(') {
						result += stk.top();
						stk.pop();
					}
					stk.push(input[i]);
								
				}
				else if (input[i] == '*' || input[i] == '/') {
					while (!stk.empty() && (stk.top() == '*' || stk.top() == '/')) {
						result += stk.top();
						stk.pop();
					}
					stk.push(input[i]);
					
				}


			}

		}

	}

	while (!stk.empty()) {
		result += stk.top();
		stk.pop();
	}

	cout << result << endl;
	return 0;
}