후위식 만들기

후위식을 만들기 위해서는 스택을 활용 해야한다.

스택은 후위식으로 만들때와 계산할 때 둘다 활용 할 수 있다.

스택 연산자의 우선순위가 높은 경우

스택 연산자를 출력한 후 pop

아니라면 push

여는 괄호는 ‘(’ 가장 낮은 우선순위이다.

닫힌 괄호 ‘)’이 나온다면 ‘(’이 나올 때 까지 pop

숫자는 계속 출력하면 된다.

계산 할때는 피연산자는 push

연산자가 나오면 스택에서 두 개의 피연산자를 pop 한다

단 나누기나 빼기처럼 순서가 중요한 연산자의 경우 두 개의 피연사자의 순서를 바꾼다

수행한 결과를 스택에 push

스택에 하나가 남는 다면 그것이 결과 이다.

코드

"MyArrayStack.h"

#ifndef __MY_ARRAY_STACK_HPP__
#define __MY_ARRAY_STACK_HPP__
#include <cstdio>
#include <cstdlib>
#define STACK_LEN 100
template <typename T>
class ArrStack {
private:
	T* arr;
	int length;
	int top;
public:
	ArrStack() {
		top = -1;
		length = STACK_LEN;
		arr = new T[STACK_LEN];
	}
	ArrStack(int len) {
		top = -1;
		length = len;
		arr = new T[len];
	}
	void Stack_Init() //배열 스택 초기화
	{
		top = -1;
	}
	void Stack_Push(T item) //데이터 삽입
	{
		if (!Stack_IsFull()) { //스택이 가득 찼을 때
			top++;
			arr[top] = item;
		}
		else
		{
			printf("Stack is full!\\n");
			exit(1);
		}
	}
	T Stack_Pop() //데이터 인출
	{
		int idx;
		if (Stack_IsEmpty()) { //스택이 비었을 때
			printf("Stack is empty!\\n");
			exit(1);
		}
		else
		{
			idx = top;
			top--;
			return arr[idx];
		}
	}
	T Stack_Peek() //최상단 데이터 확인
	{
		if (Stack_IsEmpty()) { //스택이 비었을 때
			printf("Stack is empty!\\n");
			exit(1);
		}
		return arr[top];
	}
	bool Stack_IsEmpty() //스택이 비어있는지 확인
	{
		if (top == -1) {
			return true;
		}
		else
		{
			return false;
		}
	}
	bool Stack_IsFull() //스택이 가득 차 있는지 확인
	{
		if (top == STACK_LEN - 1) {
			return true;
		}
		else {
			return false;
		}
	}
}; //Array Stack 클래스 선언
#endif

소스.cpp

#include <iostream>
#include <cstring>
#include "MyArrayStack.h"
using namespace std;
int IsDigit(char token) {
	switch (token) //연산자가 아니면 피연사자로
	{
	case '*':
	case '/':
	case '+':
	case '-':
	case '(':
	case ')':
		return 0;
	default:
		return 1;
	}
}
int IsOperator(char token) {
	switch (token) //피연사자면 리턴 1
	{
	case '*':
	case '/':
	case '+':
	case '-':
		return 1;
	default:
		return 0;
	}
}
int Priority(char op) {
	switch (op) //각각 우선순위 정해주기 '('는 가장 낮은 우선순위 갖기
	{
	case '*':
	case '/':
		return 3;
	case '+':
	case '-':
		return 2;
	case '(':
		return 1;
	}
}
void Infix2Postfix(const char* infix_exp, char* postfix_exp) {
	ArrStack<char> stack; //클래스 불러오기
	char token;
	stack.Stack_Init(); //스택 만들기
	int k = 0;
	char print[100];
	for (int i = 0; i < strlen(infix_exp); i++) {
		token = infix_exp[i];
		if (IsDigit(token) == 1) { //token이 숫자이면
			print[k++] = token;
		}
		else if (IsOperator(token) == 1) //token이 연산자이면
		{
			
			while (!stack.Stack_IsEmpty() && Priority(token) <= Priority(stack.Stack_Peek())) {
				print[k++] = stack.Stack_Pop(); //스택안에 연산자의 우선순위가 크거나 같으면
			}
			stack.Stack_Push(token); //아니면 푸쉬
		}
		else if (token == '(') {
			stack.Stack_Push(token); //'('를 만나면
		}
		else if (token == ')'){ // '('를 만날때 까지 팝
			while (stack.Stack_Peek() != '(')
			{
				print[k++] = stack.Stack_Pop();
			}
			stack.Stack_Pop(); //'('스택에서 지우기
		}
	}
	while (!stack.Stack_IsEmpty())
	{
		print[k++] = stack.Stack_Pop();
	}
	print[k] = '\\0'; //문자열은 널문자로 구분하기 때문에
	strcpy(postfix_exp, print); //postfix에 문자열 복사하기
}
int Eval_Postfix(char* postfix_exp) {
	ArrStack<char> stack;
	char token;
	stack.Stack_Init();
	int A = 0;
	int B = 0;
	int result = 0;
	for (int i = 0; i < strlen(postfix_exp); i++) {
		char token = postfix_exp[i];
		if (IsDigit(token)) {
			stack.Stack_Push(token - '0'); //token은 문자열이기 때문에 아스키코드 값만큼 빼주기
		}
		else if (IsOperator(token)) {
			B = stack.Stack_Pop(); //스택 순서 바꾸기
			A = stack.Stack_Pop();
			switch (token) //각 연산자마다 계산 수행해서 스택에 push
			{
			case '+':
				result = A + B;
				break;
			case '-':
				result = A - B;
				break;
			case '*':
				result = A * B;
				break;
			case '/':
				result = A / B;
				break;
			}
			stack.Stack_Push(result);
		}
	}
	return stack.Stack_Pop(); //결과값 리턴하기
} // 후위식 계산 및 결과

int main(void) {
	char exp[] = "(2+5)*(3+4)-(2+(7-5))"; //계산할 수식
	char* postfix = new char[strlen(exp) + 1]; //후위식 변환 결과
	//1) 중위식에서 후위식으로 변환
	Infix2Postfix(exp, postfix); //중위식에서 후위식으로 변환
	printf("Infix: %s\\n", exp);
	printf("Postfix: %s\\n", postfix); //변환 결과 출력
	//2) 변환된 후위식을 계산
	int result = Eval_Postfix(postfix);
	printf("%s = %d \\n", postfix, result);
	return 0;
}