[백준] 백준 문제 풀이 - 1918 후위 표기법

👩🏻‍💻 문제링크

 

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

1918번: 후위 표기식

 

✍️ 아이디어

1. 문제 이해

• 책에서 배운 후위 표기법을 생각하면 되겠구만
• 우선순위 낮은 녀석(+ , -)이 스택 밑에 깔리고 높은 녀석(* , /)이 위로 올라감

2. 실수한점 : ( 가 나오면 우선순위 상관없이 무조건 스택에 넣었다가 )가 나와야만 연산자가 나올수 있다고 생각함

-> 이러한 생각으로 bool을 이용해서 ( 가 들어온 상태와 안들어온 상태를 나눌려고 했었는데 의미 없는 짓이었음

✍️소스코드

다른 사람들 코드도 다 비슷함

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

int main()
{
	string exp; cin>>exp;
	vector <char> result; //후위표기법을 저장할 공간
	stack <char> stk;
	for(char ch : exp)
	{
		if(ch>=65 && ch<=90) // 숫자이면 무조건 결과값에 넣음
		{
			result.push_back(ch);
		}
		
		else //연산자인 경우
		{
			if((ch == '+' || ch == '-') && !stk.empty()) // +, - 는 우선순위가 낮다
			{
				while(!stk.empty() && stk.top() != '(') //주의 !!!! (가 있다면 ( 전까지만 꺼내야한다
				{
					result.push_back(stk.top());
					stk.pop();
				}
				stk.push(ch);
			}
			else if((ch == '*' || ch == '/') && !stk.empty())
			{
				while((stk.top() == '*' || stk.top() == '/') && !stk.empty() && stk.top() != '(')
				{
					result.push_back(stk.top());
					stk.pop();
				}
				stk.push(ch);
			}
			else if(ch == '(') //( 가 나오면 일단 넣는다
			{
				stk.push(ch);
			}
			else if(ch == ')') //)면 괄호가 끝난거니까 무조건 안에 있는거 다 끄집어 내야함
			{
				while(!stk.empty() && stk.top() != '(')
				{
					result.push_back(stk.top());
					stk.pop();
				}
				stk.pop();
			}
			else
			{
				stk.push(ch);
			}
		}
	}
	
	while(!stk.empty())
	{
		result.push_back(stk.top());
		stk.pop();
	}
	
	for(auto iter = result.begin(); iter!= result.end(); iter++)
	{
		cout<<*iter;
	}
	cout<<'\n';
}

 

내가 헷갈렸던 부분 :  while(!stk.empty() && stk.top() != '(')  +나 -는 다 꺼내버릴수도 있으니까 ( 나오면 멈추게 설정해야함

 

체감난이도	걸린시간	참고	사용 문법
중상	1hour	x	스택