c++ 백준_1918_"후위 표기식"

https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

 

문제를 보다가

오랜만에

쓰-때압 을 이용한

Infix to Postfix 를 해보았다.

​

예전에 자료구조 공부할 때 열심히 봐야했던 알고리즘이

Gold3이라니 너무하네

​

복습하는 식으로 했는데

간만에 보니 좀 헷갈렸다

​

​

​

일단 연산자마다 우선순위를 둬야지

비교하며 stack에서 꺼낼지말지 정한다.

​

연산자가 [ +, -, *, / ] 일 때

현재 연산자와

stack 내부, top 에 있는 연산자의 우선순위를 비교한다.

(ex. 현재 연산자가 '+'이고 , stack top에 있는 연사자가 '*'라면

stack 내부에 있는 연산자가 우선순위가 더 높기에

pop 및 출력을 해줘야한다.)

모든 비교 및 출력이 끝나면 현재 연산자는 stack 에 넣어준다.

​

그리고 현재 연산자가

'(' 일 경우

스택에 넣고,

​

')' 일 경우

먼저 넣은 '(' 가 나오기 전까지

모두 pop 및 출력한다.

​

연산자가 아닌 숫자(여기서는 알파벳)는

바로바로 출력해준다.

 

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

int prec(char op) {
	switch (op){
	case '(':case')': return 0;
	case'+':case'-':return 1;
	case '*':case'/': return 2;
		return -1;
	}	
}

void infix_to_postfix(string exp) {

	int len = exp.size();
	stack<char> st;

	for (int i = 0; i < len; i++) {
		char ch = exp[i];

		switch (ch) {
		case '+':case'-': case'*':case'/':
			while (!st.empty() && (prec(ch) <= prec(st.top()))) {
				cout << st.top();
				st.pop();
			}
			st.push(ch);
			break;
		case '(':
			st.push(ch);
			break;
		case')':
			while (st.top() != '(') {
				cout << st.top();
				st.pop();
			}
			st.pop();
			break;
		default:
			cout << ch;
			break;
		}
	}
	while (!st.empty()) {
		cout << st.top();
		st.pop();
	}
}

int main(void) {

	string exp;

	cin >> exp;

	infix_to_postfix(exp);


}