자료구조 stack을 이용한 문제 풀이 1(postfix)

우리는 후위표기식에 대해 알아볼 것이다. 후위 표기식이란 컴퓨터가 알아보기 쉽게 하는 표기 방식으로

우리가 흔히 연산을 표시하는 표시 방법인 중위 표기식과는 사뭇 다르게 생겼다.

예를 들어 중위 표기식에서 3+5 와 같은 식을 후위 표기식으로 표시하게 되면 3,5+와 같이 표기된다.

좀 더 복잡한 중위 표기식 예를 들면 A+B-C*D와 같은 경우에서는 연산 우선 순위가 *가 가장 높으므로 이것부터 처리해준다.

A+B-CD* -> AB+-CD*>AB+CD*- 와 같이 변하게 된다. 이것이 후위 표기법이다.

몇 가지의 예시를 더 살펴보겠다.

1. A+B*C -> A+BC*

2. A*B-C -> AB*-C -> AB*C-

이와 같이 컴퓨터는 순서대로 읽으므로 컴퓨터가 읽기 쉽도록 표기법을 수정하는 것이다.

​

괄호의 경우에도 문제가 된다. 괄호는 항상 우선으로 계산해야하므로 어딘가에 괄호가 있다는 것을 저장해 둘 장소가 필요하다. 이 때 사용되는 것이 자료구조에서의 stack이다. stack은 Last in First Out의 구조로서 어떤 통안에 자료를 차곡차곡 쌓았다가 넣은 순서에 반대로 빼내는 자료구조를 의미한다.

​

나는 if문을 사용하여 postfix 변환 코드를 작성하였지만 case문을 사용하는 것이 훨씬 간결하고 쉽다.

​

우선 A+B+C -> AB++C->ABC++에서 A(operand)인지 +(operator)인지를 판단하는 함수들이 필요하다.

나는 bool타입을 이용해 operator인지 operand인지 판단하는 함수를 작성하였다.

 

bool isoperand(string c) // 12171800 심정호
{
	if ((c >= "a" && c <= "z") || (c >= "A" && c <= "Z")) // 다음과 같은 문자열을 입력받으면 이것은 operand로 판별한다.
	{
		return true;
	}
	else
		return false;
}
bool isoperator(string c)
{
	if (c == "+" || c == "-" || c == "*" || c == "/" || c == "^" || c == "(" || c == ")" || c == "") // 다음과 같은 문자열을 입력받으면 operator로 판별한다. 
	{
		return true;
	}
	else
		return false;
}

또한 곱셈과 나눗셈 더하기 빼기는 각각 우선순위가 존재하므로 우선순위를 나타내주는 함수를 작성하였다.

식 내에서의 우선 순위와 stack내에서의 우선 순위는 다르다. 스택에 operator들을 저장해줄 때 우선순위가 높은 연산자부터 출력되어야하므로 우선순위가 낮은 연산자가 우선 순위가 높은 연산자 위에 들어올 경우에는 우선 그 높은 연산자를 꺼내어 출력하고 들어오는 연산자보다 stack에 남아있는 연산자의 우선순위가 낮을 때까지 이 작업을 반복한다.

​

혹은 들어오는 연산자의 우선 순위가 stack내의 top에 위치하는 연산자보다 우선순위가 높다면 그대로 push하여 스택의 top이 되도록 한다.

 

괄호의 경우에는 후위 표기식에서는 출력이 되지 않으므로 stack내부에서 존재만 하지 pop되어서 꺼내져 나올 때 화면에 표시하지는 않는다.

int pis(string str) // stack 내에서의 연산자들의 우선 순위
{
	if (str == "(") // 12171800 심정호
		return 0;
	else if (str == "+" || str == "-")
		return 1;
	else if (str == "*" || str == "/")
		return 2;
	else if (str == "^")
		return 3;
	else
		return 4;
}
int pie(string str) // 식 내에서의 연산자들의 우선 순위
{
	if (str == "+" || str == "-")
		return 1;
	else if (str == "*" || str == "/")
		return 2;
	else if (str == "^")
		return 3;
	else if (str == "(" || str == ")")
		return 4;

}
void prefixtopostfix(string postfix)
{
	DequeStack a; // operator를 저장할 stack을 생성한다.
	string st; // 입력받을 문자열
	for (int i = 0; i <= postfix.length(); i++) // 입력받은 문자열의 길이만큼 반복한다.
	{
		st = postfix[i]; // 입력받은 문자열의 i번째에 있는 char형 문자를 다시 string자료형으로 변환한다.
		if (isoperand(st)) // 만약 입력받은 문자열이 operand라면 그대로 출력한다.
		{
			cout << postfix[i] << " ";
		}

		if (isoperator(st)) // 만약 입력받은 문자열이 operator라면 우선 stack이 비어있는 지 아닌 지를 판별한다.
		{

			if (a.empty()) // 만약 비어있다면 어떤 operator인지 상관 없이 stack에 push한다.
			{
				a.push(st);
			}
			else {
				if (pis(a.top()) < pie(st)) // 비어 있지 않다면 stack내에서 가장 위에 있는 operator의 pis리턴값이 새로들어오는 operator의 식에서의 우선 순위보다 작다면
				{
					a.push(st); // 그냥 stack에 push한다.
				}
				else // 만약 아니라면
				{
					while (pis(a.top()) >= pie(st)) // stack내 가장 위에 있는 operator의 pis가 식에서 들어오는 operator의 pie보다 작아질 때 까지 stack내의 가장 위에 있는 원소를 출력한 다음 꺼낸다. 
					{
						if (a.top() == "(")
						{
							a.push(st);
						}
						else {
							cout << a.top() << " ";
							a.pop();
						}
						if (a.empty() || a.top() == "(") // 만약 다 꺼내서 stack이 비게 된다면 새로 들어오는 operator를 stack에 집어넣고 while루프를 끝낸다. 
						{
							a.push(st);
							break;
						}
					}
				}
			}


		}
		if (st == ")") // 만약 들어오는 연산자가 )라면 (가 나올 떄 까지 stack내의 모든 원소를 출력한 후 꺼낸다. 
		{

			while (a.top() != "(")//12171800 심정호
			{
				if (a.top() == ")") // )연산자는 출력 되지 않게 바로 꺼낸다.
				{
					a.pop();
				}
				cout << a.top() << " ";
				a.pop();
			}
			if (a.top() == "(")
			{
				a.pop();
			}
		}


		if (i == postfix.length()) // 마지막 루프에서 stack내에 들어있는 모든 원소를 꺼낸다. 
		{
			while (a.size() > 0)
			{
				cout << a.top() << " ";
				a.pop();
			}
			cout << " ";
		}

	}
}