[자료구조] 사칙연산 계산기 구현

간단한 사칙연산 계산기 구현입니다.

C, C++을 통해서 계산기를 구현한 코드입니다.

 

먼저 알아야할 개념은 두가지 입니다.

1. 자료구조 스택 (LIFO)

2. 수의 중위 표기법, 전위 표기법, 후위 표기법

 

중위 표기법은 1+2*3 과같은 저희가 사용하는 수식입니다.

전위 표기법은 +1*23

후위표기법은 123*+ 입니다.

 

순서는 "Stack 자료구조 구현 => 중위 표현식을 후위 표현식으로 변경 => 후위 표현식을 계산" 입니다.

 

스택의 중위 => 후위로 변경할 때 사용하는 자료구조 입니다.

연산자의 우선순위가 높다면 스택에 쌓아두고 그렇지 않다면 현재 스택에서 pop() 을 진행한뒤 쌓아둡니다.

후위 표기법의 계산은 12+3*순일경우 앞에 있는 수 12를 차례대로 끄집어 낸다음 뒤에오는 '+' 연산자를 통해 1 + 2를 진행합니다.이후 3을 다시 스택에 넣고 33*을 계산하는데 12+와 마찬가지로 3을 꺼내고 3을 다시 꺼내고 '*' 를 통해서 3 * 3을 계산하여 반환합니다.

 

저희가 사용할 표기법은 후위 표기법입니다. 

(후위 표기법 개념은 https://simsim231.tistory.com/54 에 정리가 되어있습니다!)

 

---

스택 자료구조 선언과 정의

Stack.h

#pragma once

#define STACK_LEN 100

typedef int Data;

typedef struct _arrayStack
{
	Data stackArr[STACK_LEN];
	int topIdx;
} ArrayStack;

typedef ArrayStack Stack;

void StackInit(Stack* stack);
bool IsEmpty(Stack* stack);

void Push(Stack* stack, Data data);
Data Pop(Stack* stack);
Data Peek(Stack* stack);

 

Stack.cpp

#include "Stack.h"
#include <stdlib.h>
#include <iostream>

void StackInit(Stack* stack)
{
	stack->topIdx = -1;
}

bool IsEmpty(Stack* stack)
{
	if (stack->topIdx == -1) return true;
	else return false;
}

void Push(Stack* stack, Data data)
{
	stack->topIdx += 1;
	stack->stackArr[stack->topIdx] = data;
}

Data Pop(Stack* stack)
{
	int ridx = -1;
	
	if (IsEmpty(stack))
	{
		std::cout << "Stack Memory Error!" << std::endl;
		exit(-1);
	}
	
	ridx = stack->topIdx;
	stack->topIdx -= 1;
	return stack->stackArr[ridx];
}

Data Peek(Stack* stack)
{
	if (IsEmpty(stack))
	{
		std::cout << "Stack Memory Error!" << std::endl;
		exit(-1);
	}

	return stack->stackArr[stack->topIdx];
}

 

후위 표현식으로 바꿔주는 Cal.h 선언 및 정의

#pragma once
#include <string>
#include <stdlib.h>
#include "Stack.h"

// GetPrecedeOperation
int GPO(char op)
{
	switch (op)
	{
	case '*':
	case '/':
		return 3;
	case '+':
	case '-':
		return 2;
	case '(':
		return 1;
	}

	return -1;
}

// Who Is Precede Operation
int WIPO(char op1, char op2)
{
	int op1P = GPO(op1);
	int op2P = GPO(op2);
	
	if (op1P > op2P) return 1;
	else if (op1P < op2P) return -1;
	else return 0;
}

// Convert To RPNE 후위 연산자로 변형
void ConvToR(char exp[])
{
	Stack stk;
	int expLen = strlen(exp);

	// char* convExp = (char*)malloc(expLen + 1);
	char* convExp = new char[expLen + 1];

	int i, idx = 0;
	char tok, popOp;

	memset(convExp, 0, sizeof(char)*expLen + 1);
	StackInit(&stk);

	for (int i = 0; i < expLen; ++i)
	{
		tok = exp[i];
		if (isdigit(tok))
		{
			convExp[idx++] = tok;
		}
		else
		{
			switch (tok)
			{
				case '(':
					Push(&stk, tok);
					break;
				case ')':
				{
					while (1)
					{
						popOp = Pop(&stk);
						if (popOp == '(') break;

						convExp[idx++] = popOp;
					}
				}
				break;
				case '+': case '-':
				case '*' : case '/':
				{
					while (!IsEmpty(&stk) && WIPO(Peek(&stk), tok) >= 0)
					{
						convExp[idx++] = Pop(&stk);
					}
					
					Push(&stk, tok);
				}
				break;
			}
		}
	}
	while (!IsEmpty(&stk))
	{
		convExp[idx++] = Pop(&stk);
	}

	for (int i = 0; i < expLen; ++i)
	{
		exp[i] = convExp[i];
	}

	// free(convExp);
	delete[] convExp;
}

 

후위 표현식을 계산해주는 GetRPNEValue.h 선언 및 정의

#pragma once
#include "Stack.h"
#include <string.h>
#include <ctype.h>

int GetRPNE(char exp[])
{
	Stack stk;
	int expSize = strlen(exp);
	int i = 0;
	char tok, op1, op2 = '\0';
	
	StackInit(&stk);

	for (i = 0; i < expSize; ++i)
	{
		// 12+
		tok = exp[i];

		if (isdigit(tok))
		{
			Push(&stk, tok - '0');
		}
		else
		{
			op2 = Pop(&stk);
			op1 = Pop(&stk);

			switch (tok)
			{
			case '+':
				Push(&stk, op1 + op2);
				break;
			case '-':
				Push(&stk, op1 - op2);
				break;
			case '*':
				Push(&stk, op1 * op2);
				break;
			case '/':
				Push(&stk, op1 / op2);
				break;
			}
		}
	}
	return Pop(&stk);
}

 

main.cpp 에서 실행

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

#define endl "\n"

#include "Stack.h"
#include "Cal.h"
#include "GetRPNEValue.h"

int main()
{
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	cout.tie(NULL);
	
	char e1[] = "1+2*3";
	char e2[] = "(1+2)*3";
	char e3[] = "((1-2)+3)*(5-2)";

	ConvToR(e1);
	ConvToR(e2);
	ConvToR(e3);

	cout << e1 << endl;
	cout << e2 << endl;
	cout << e3 << endl;

	cout << GetRPNE(e1) << endl;
	cout << GetRPNE(e2) << endl;
	cout << GetRPNE(e3) << endl;
	
	return 0;
}