TIL Blog💻

[BOJ] 후위 표기식(1918)

  • Sep 01, 2020

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

문제 : BOJ_1918번 후위 표기식

문제 설명

Stack

중위 표기식으로 예제가 주어지면 이것을 후위 표기식으로 바꾸는 문제입니다.
피연산자는 알파벳 대문자만 나오며, ‘-‘가 가장 앞에 나오거나, ‘*‘가 생략되는 입력은 허용하지 않습니다.
stack을 상황에 맞게 활용해서 풀어야 하는 문제입니다.

Solution

전체 문자열을 입력받고 아래와 같은 규칙으로 순회합니다.

  • 피연사자는 무조건 화면에 출력한다.
  • ’(‘가 나오면 stack에 push 한다.
  • ’)’가 나오면 ‘(‘가 나올 때까지 stack을 비우며 출력한 뒤, 마지막 ‘(‘도 출력 없이 pop 해준다.
  • 연산자가 나왔을 때 stack에 top에 자신보다 우선순위가 같거나 높은 연산자가 있으면 그 연산자를 pop 해주고 화면에 출력한다.
  • 우선순위가 같거나 높은 연산자가 나오지 않고 ‘(‘나 stack이 빌 때까지 계속 pop 해주다가 만나게 되면 push 해준다.

Description

  • (int i = 0; str[i] != '\0'; i++)로 전체 문자열을 순회했습니다.
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
stack<char> s;
int main(void) {
	char str[101];
	cin >> str;
	stack<char> s;
	for (int i = 0; str[i] != '\0'; i++) {
		char value=str[i];
		if (value <= 'Z' && 'A' <= value) cout << value;
		else if (value == '(') s.push(value);
		else if (value == ')') {
			while (s.top() != '(') {
				cout << s.top();
				s.pop();
			}
			s.pop();
		}
		else if (s.empty()) s.push(value);
		else {
			while (!s.empty()) {
				if (s.top() == '(') {
					s.push(value);
					break;
				}
				else if (value == '+' || value == '-') {
						cout << s.top();
						s.pop();
						continue;
				}
				else if (value == '*' || value == '/') {
					if (s.top() == '*' || s.top() == '/') {
						cout << s.top();
						s.pop();
						continue;
					}
					else {
						s.push(value);
						break;
					}
				}
			}
			if (s.empty()) s.push(value);
		}
	}
	while (!s.empty()) {
		cout << s.top();
		s.pop();
	}
	cout << '\n';
	return 0;
}
Search