[C++] 자료구조 7주차 과제5

간단한 수식을 입력 받아서 계산을 해주는 계산기 프로그램을 작성한다.

반드시 Template 클래스와 스택을 사용하여 구현한다.

자세한 내용은 첨부한 pdf 파일을 참조하여 작성한다.

#문자열 입력으로 .이 입력될 때까지 재입력을 받도록 한다.

#헤더와 메인 파일은 분리하지 않고 한 개의 cpp파일을 제출한다. 

#입력값을 반복적으로 받을 수 있게 하고, .(마침표)를 입력하면 프로그램을 종료하도록 한다.

 

입력: 중위표기식 수식인 문자열

출력: 수식 계산 결과값, 입력 수식의 후위표기식

 

Code

#include <iostream>
#include <string>
#include <algorithm>
 
using namespace std;
 
template <class T>
class Stack {
public:
	Stack(int stackCapacity = 10);
	bool IsEmpty() const;
	T& Top() const;
	void Push(const T& item);
	void Pop();
 
private:
	T* stack;
	int top;
	int capacity;
};
 
template <class T>
Stack<T>::Stack(int stackCapacity) :capacity(stackCapacity)
{
	if (capacity < 1) throw "Stack capacity must be >= 0";
	stack = new T[capacity];
	top = -1;
}
 
template <class T>
void ChangeSize(T*& arr, const int oldsize, const int newsize)
{
	if (newsize < 0) throw "New length must be >= 0";
 
	T* temp = new T[newsize];
	int number = min(oldsize, newsize);
	copy(arr, arr + number, temp);
	delete[]arr;
	arr = temp;
}
 
template <class T>
inline bool Stack<T>::IsEmpty() const { return top == -1; }  // stack에 원소가 없다면 true, 있으면 false
 
template <class T>
inline T& Stack<T>::Top() const
{
	if (IsEmpty()) throw "Stack Empty";
	return stack[top];
}
 
template <class T>
void Stack<T>::Push(const T& x)
{
	if (top == capacity - 1)
	{
		ChangeSize(stack, capacity, 2 * capacity);
		capacity *= 2;
	}
	stack[++top] = x;
}
 
template <class T>
void Stack<T>::Pop()
{
	if (IsEmpty()) throw "Stack Empty. Cannot delete";
	stack[top--].~T();  // T에 대한 파괴자
}
 
int ICP(char t)  // In coming Priority
{
	// 계산기에 입력될 수식에 쓰일 연산자에 대해서만 우선순위 설정.
	// 음수부호- 는 입력조건이 0~9 이므로 고려하지 않는다.
 
	if (t == '(') return 0;
	else if (t == '*' || t == '/' || t == '%') return 2;
	else if (t == '+' || t == '-') return 3;
	else if (t == '#') return 8;
}
 
int ISP(char t)  // In Stack Priority
{
	if (t == '(') return 8;
	else if (t == '*' || t == '/' || t == '%') return 2;
	else if (t == '+' || t == '-') return 3;
}
 
string postfixResult;  // 후위표기식 변환결과를 따로 string으로 저장(global)
 
void Postfix(string exp)  // 중위표기식 -> 후위표기식 변환
{
	Stack<char> tokenStack;
	tokenStack.Push('#');
 
	for (int i = 0; (exp[i] != '#') && (i < exp.length()); i++)
	{
		char t = exp[i];
 
		if (isdigit(t))
		{
			cout << t << " ";  // 0~9 정수라면 그냥 그대로 출력
			postfixResult.push_back(t);
		}
 
		else if (t == ')') 
		{
			for (; tokenStack.Top() != '('; tokenStack.Pop()) {
				cout << tokenStack.Top() << " ";  // '(' 전 까지 출력
				postfixResult.push_back(tokenStack.Top());
			}
			tokenStack.Pop();  // unstack '('
		}
 
		else 
		{
			for (; ISP(tokenStack.Top()) <= ICP(t); tokenStack.Pop()) {
				// 앞에 들어올 연산자의 우선순위가 현재 연산자의 우선순위보다 작으면 출력 후 Pop
				cout << tokenStack.Top() << " ";
				postfixResult.push_back(tokenStack.Top());
			}
			tokenStack.Push(t);
		}
	}
 
	while (tokenStack.Top() != '#')  // #을 제외하고 출력
	{
		cout << tokenStack.Top() << " ";
		postfixResult.push_back(tokenStack.Top());
		tokenStack.Pop();
	}
	cout << endl;
}
 
float Eval(string postfix)
{
	// 앞에서부터 읽으며 피연산자는 스택에 쌓는다.
	// 연산자를 만나면 스택에서 피연산자 2개를 꺼내 연산을 수행하고 다시 스택에 쌓는다.
	// 끝날 때까지 계속 반복
 
	Stack<float> operandStack;  // 나눗셈 고려해서 float
	float result = 0;
	
	for (int i = 0; i < postfix.length(); i++)
	{
		char t = postfix[i];
 
		if (isdigit(t)) operandStack.Push(t - '0');  // char 데이터형을 int로 변환하기 위해 -'0'
 
		else
		{
			float op1 = operandStack.Top();
			operandStack.Pop();
			float op2 = operandStack.Top();
			operandStack.Pop();
 
			float temp = 0;  // 스택에 쌓을 연산결과를 담을 변수
			if (t == '+') temp = op2 + op1;
			if (t == '-') temp = op2 - op1;
			if (t == '*') temp = op2 * op1;
			if (t == '/') temp = op2 / op1;
			operandStack.Push(temp);
		}
	}
 
	result = operandStack.Top();
	operandStack.Pop();
 
	return result;
}
 
int main()
{
	cout << "> ";
	while (1) {
		string infix;  // 중위표기식 입력받기
		cin >> infix;
		if (infix[0] == '.') exit(0);  // . 입력시 종료
		Postfix(infix);
		cout << Eval(postfixResult) <<'\n' << endl;
		cout << "> ";
	}
 
	return 0;
}

실행결과

 

점수 10/10

 

 

  ❤와 댓글은 큰 힘이 됩니다. 감사합니다 :-)