1224. [S/W 문제해결 기본] 6일차 - 계산기3

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14tDX6AFgCFAYD&categoryId=AV14tDX6AFgCFAYD&categoryType=CODE

SW Expert Academy

 

 

후위표기식 계산 방법

1  숫자는 출력

2. 빈 스택 혹은 ( 시작괄호는 무조건 push

3. ) 인 경우 ( 전까지 쌓인 연산 출력

4. *, + 연산의 경우 자신보다 우선순위가 높은 것이 스택에 남아 있으면 전부 출력

*같은 경우는 그냥 push하면 되고 +는 top에 *가 있다면 전부 출력해야 한다.

이 때, 빈 스택인데 top 참조하는 경우 예외 주의

이렇게 만들어진 후위 표기 식은 

stack을 이용하여 계산 가능.

abc++이라면 bc+되고 그결과와 a가 + 되므로 연산결과는 계속 스택의 top에 올려지면 되고 , 

그 외 숫자가 들어올 때마다 top이 밀리면 됨.

 

#include<iostream>
#include<string.h>
#include<vector>
#include<stack>
#include<sstream>

using namespace std;

string str;

int main(int argc, char** argv)
{
	int test_case;

	for (test_case = 1; test_case <= 10; ++test_case)
	{
		int size;
		vector<char> result;
		stack<char> sta;
		cin >> size >> str;
		

		for (int i = 0; i < str.size(); i++)
		{
			if (str[i] >= '0' && str[i] <= '9')
			{
				result.push_back(str[i]);

			}
			else if (sta.empty() || str[i] == '(')
			{
				sta.push(str[i]);
			}
			else if (str[i] == ')')
			{
				while (sta.top() != '(')
				{
					result.push_back(sta.top());
					sta.pop();
				}
				sta.pop();
			}
			else
			{
				if (str[i] == '*')
				{
					sta.push(str[i]);
				}
				else
				{
					while (!sta.empty() && sta.top() == '*')
					{
						result.push_back(sta.top());
						sta.pop();
					}
					sta.push(str[i]);
				}
			

			}

		}
		while (!sta.empty())
		{
			result.push_back(sta.top());
			sta.pop();
		}
		int length = result.size();
			
		stack<int>num;

		for (int i = 0; i < length; i++)
		{
			if (result[i] >= '0' && result[i] <= '9')
			{
				num.push(result[i] - '0');
			}
			else if (result[i] == '+')
			{
				int a = num.top();
				num.pop();
				int b = num.top();
				num.pop();
				int z = a + b;
				num.push(z);

			}
			else if (result[i] == '*')
			{
				int a = num.top();
				num.pop();
				int b = num.top();
				num.pop();
				int z = a * b;
				num.push(z);

			}
		}

		cout << "#" << test_case << " " << num.top() << endl;

	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}