Dutor

template <class T>   
 
class Stack   
{   
public:   
	Stack(int stack_size = 30);   
	~Stack();   
	void Push(T value);   
	T Pop();   
	T Top();   
	bool IsEmpty();   
	bool IsFull();   
	void ClearStack();   
private:   
	int top;   
	T* stack;   
	int size;   
};   
template<class T>   
Stack<T>::Stack(int stack_size)   
{   
	size = stack_size;   
	Stack::stack = new T[size];   
	Stack::top = -1;   
}   
 
template<class T>   
Stack<T>::~Stack()   
{   
	delete []stack;   
}   
 
template<class T>   
void Stack<T>::Push(T value)   
{   
	stack[++top] = value;   
}   
 
template<class T>   
T Stack<T>::Pop()   
{   
	return stack[top--];   
}   
 
template<class T>   
T Stack<T>::Top()   
{   
	return Stack[top];   
}   
 
template<class T>   
bool Stack<T>::IsEmpty()   
{   
	return(top==-1?true:false);   
}   
 
template<class T>   
bool Stack<T>::IsFull()   
{   
	return(top==(size-1)?true:false);   
}   
 
template<class T>   
void Stack<T>::ClearStack()   
{   
	top = -1;   
}

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include "Stack.h"
 
using namespace std;
 
class Calculate
{
public:
	Calculate();
	~Calculate();
	int Cal(string express);
private:
	string ParseString(string express);
	vector<string> MidToBehind(string express);
	int Compute(int a,int b,char operater);
	Stack<int> stack_int;
	Stack<char> stack_char;
};

Calculate::Calculate()
{
 
}
 
Calculate::~Calculate()
{
 
}
 
vector<string> Calculate::MidToBehind(string express)
{
	stringstream strstrm(express);
	char temp_char;
	string temp_str;
	vector<string> result_vec;
	while (strstrm>>temp_char)
	{
		if (temp_char!='('&&temp_char!=')'&&temp_char!='+'&&temp_char!='-'&&temp_char!='*'&&temp_char!='/'&&temp_char!='=')
		{
			strstrm.putback(temp_char);
			strstrm>>temp_str;
			result_vec.push_back(temp_str);
		}
		else if(temp_char == '(')
		{
			stack_char.Push(temp_char);
		}
		else if(temp_char == ')')
		{
			if(stack_char.IsEmpty())
			{
				cout<<"stack is empty when push ')'"<<endl;
				stack_char.ClearStack();
			}
			else
			{
				while (temp_char = stack_char.Pop(),temp_char != '(')
				{
					result_vec.push_back(string(1,temp_char));
					if (stack_char.IsEmpty())
					{
						cout<<"stack is empty when pop,not found the '('"<<endl;
						stack_char.ClearStack();
					}
				}
			}
		}
		else if(temp_char == '+'||temp_char == '-'||temp_char == '*'||temp_char == '/')
		{
			switch (temp_char)
			{
				char temp_char_2;
			case '+':
				while (!stack_char.IsEmpty())
				{
					temp_char_2 = stack_char.Pop();
					if (temp_char_2 == '(')
					{
						stack_char.Push(temp_char_2);
						break;
					}
					else
						result_vec.push_back(string(1,temp_char_2));
				}
				stack_char.Push(temp_char);
				break;
			case '-':
				while (!stack_char.IsEmpty())
				{
					temp_char_2 = stack_char.Pop();
					if (temp_char_2 == '(')
					{
						stack_char.Push(temp_char_2);
						break;
					}
					else
						result_vec.push_back(string(1,temp_char_2));
				}
				stack_char.Push(temp_char);
				break;
			case '*':
				while (!stack_char.IsEmpty())
				{
					temp_char_2 = stack_char.Pop();
					if (temp_char_2 == '('||temp_char_2 == '+'||temp_char_2 == '-')
					{
						stack_char.Push(temp_char_2);
						break;
					}
					else
						result_vec.push_back(string(1,temp_char_2));
				}
				stack_char.Push(temp_char);
				break;
			case '/':
				while (!stack_char.IsEmpty())
				{
					temp_char_2 = stack_char.Pop();
					if (temp_char_2 == '('||temp_char_2 == '+'||temp_char_2 == '-')
					{
						stack_char.Push(temp_char_2);
						break;
					}
					else
						result_vec.push_back(string(1,temp_char_2));
				}
				stack_char.Push(temp_char);
				break;
			default:
				break;
			}
		}
		else if (temp_char == '=')
		{
			while (!stack_char.IsEmpty())
			{
				result_vec.push_back(string(1,stack_char.Pop()));
			}
		}
		else
			cout<<"wrong express"<<endl;
	}
	return result_vec;
}
 
int Calculate::Compute(int a,int b,char operater)
{
	switch(operater)
	{
	case '+':
		return a + b;
	case '-':
		return a - b;
	case '*':
		return a * b;
	case '/':
		if(b == 0)
		{
			cout<<"divided by 0!wrong!"<<endl;
			return -1;
		}
		else
			return a / b;
	default:
		break;
	}
	cout<<"Not return"<<endl;
	return -1;
}
 
int Calculate::Cal(string express)
{
	string new_exp = ParseString(express);
	string str_temp;
	vector<string> vec_exp = MidToBehind(new_exp);
	for (vector<string>::iterator it = vec_exp.begin();it != vec_exp.end();it++)
	{
		str_temp = *it;
		if (str_temp!="+"&&str_temp!="-"&&str_temp!="*"&&str_temp!="/")
		{
			int int_temp = 0;
			int time = 1;
			for (string::iterator itr = str_temp.begin();itr != str_temp.end();itr++)
			{
				int_temp = int_temp*10 + (*itr - '0');
			}
			stack_int.Push(int_temp);
		} 
		else
		{
			int a,b;
			b = stack_int.Pop();
			a = stack_int.Pop();
			char ch = str_temp[0];
			int c = Compute(a,b,ch);
			stack_int.Push(c);
		}
	}
	return stack_int.Pop();
}
 
string Calculate::ParseString(string express)
{
	string new_exp;
	bool flag = false;
	for (string::iterator it = express.begin();it != express.end();it++)
	{
		if (*it>='0'&&*it<='9')
		{
			if(flag)
				new_exp.push_back(' ');
			flag = false;
			new_exp.push_back(*it);
		}
		else
		{
			flag = true;
			if(it != express.begin())
				new_exp.push_back(' ');
			new_exp.push_back(*it);
		}
	}
	return new_exp;
}