数据结构学习----计算器程序(栈的应用)

/********************************************************************************/
/*                            计算器程序                                    */
/*                                                                              */
/*                            2010-3-8                                         */
/*                                                                              */
/*    说明: Calculator类,用于通过给定四则运算表达式, 求出表达式的代数值         */
/*                                                                              */
/*    示例: #include <iostream>                                                 */
/*          #include <string>                                                   */
/*          #include "Calculator.h"                                             */
/*          void main()                                                         */
/*			{                                                                   */
/*			   string expression="2.3+(25-0.6*3.2^1.6)/(5-1.5^2)";              */
/*			   Calculator c(expression);                                        */
/*			   cout<<c.Run()<<endl;                                             */
/*             getchar();                                                       */
/*			}                                                                   */
/*                                                                              */
/*          输出:9.98791                                                        */
/*                                                                              */
/********************************************************************************/



//节点类, 用于保存浮点数[flag=0],或者运算符[flag=1]
#pragma region
class Item
{
public:
	Item(){}                       //构造函数
	Item(string _value,int _flag)  //重载构造函数
	{
		value=_value; flag=_flag;
	}
	string value;                  //保存浮点数,或者运算符
	int  flag;                     //标志位
	Item& operator=(Item& item)    //运算符重载
	{
		value=item.value;
		flag=item.flag;
		return *this;
	}
};
#pragma endregion


/*===================================================================================*/
/*                                                                                   */
/*                            各个算术操作符的优先级                                 */
/*  ------------------------------------------------------------------------------   */
/*  |   操作符   |     #    |    (    |    ^    |    * / %    |   + -   |    )   |   */
/*  ------------------------------------------------------------------------------   */
/*  |     isp    |     0    |     1   |    7    |      5      |     3   |    8   |   */
/*  ------------------------------------------------------------------------------   */
/*  |     icp    |     0    |     8   |    6    |      4      |     2   |    1   |   */
/*  ------------------------------------------------------------------------------   */
/*                                                                                   */
/*===================================================================================*/
#pragma region
int isp(string s)
{
	if(s=="#")
		return 0;
	if(s=="(")
		return 1;
	if(s=="^")
		return 7;
	if(s=="*"||s=="/"||s=="%")
		return 5;
	if(s=="+"||s=="-")
		return 3;
	if(s==")")
		return 8;
	return -1;
}

int icp(string s)
{
	if(s=="#")
		return 0;
	if(s=="(")
		return 8;
	if(s=="^")
		return 6;
	if(s=="*"||s=="/"||s=="%")
		return 4;
	if(s=="+"||s=="-")
		return 2;
	if(s==")")
		return 1;
	return -1;
}
#pragma endregion


#pragma region
class Calculator
{
public:
	string expression;                            //要计算的表达式
	DCirList<Item> inlist;                        //存储中缀表达式的链表
	DCirList<Item> postlist;                      //存储后缀表达式的链表
	LinkStack<Item> stack;                        //存储符号的栈
	LinkStack<float> result;                      //存储结果
	Calculator(string _expression);               //构造函数
	void GetInfix();                              //取得中缀表达式
	void GetPostfix();                            //取得后缀表达式
	float Run();                                  //求结果
};
#pragma endregion

#pragma region
Calculator::Calculator(string _expression)
{
	expression=_expression;
	expression.append(1,'#');
}

/*====================================================================================*/
/*                              字符串转中缀表达式算法:                               */
/*                                                                                    */
/* 一.从字符串第一个字符开始扫描,遇到数字或小数点,累加该字符到value中,直到遇到运算符. */
/*    将value, 以及此运算符存入到中缀表达式链表.                                      */
/* 二.如果字符串的最后一位为数字, 则扫描完后,直接将value存入到中缀表达式链表.         */
/*                                                                                    */
/*====================================================================================*/

void Calculator::GetInfix()
{
	string value="";  int flag=0;   Item node1,node2;
	for(int i=0;i<expression.length();i++)
	{
		if( (int)expression[i]==46||((int)expression[i]>=48&&(int)expression[i]<=57) )
		{
			flag=0;
			value.append(1,expression[i]);
			if(i!=expression.length()-1)
				continue;
			else
			{
				node1.value=value;      node1.flag=0;
				inlist.PushBack(node1);
				break;
			}

		} 
		if(value!="")
		{
			node1.value=value;          node1.flag=0;
			inlist.PushBack(node1);
		}
		node2.value=expression[i];      node2.flag=1;
		inlist.PushBack(node2); 
		value="";
	}
}

/*====================================================================================*/
/*                           中缀表达式转化成后缀表达式算法:                          */
/*                                                                                    */
/* 一.操作符栈初始化,将结束符#进栈,然后读取中缀表达式链表的首个结点元素item.          */
/* 二.重复执行以下步骤,直到读到item.value='#', 同时栈顶的操作符也是#, 停止循环.       */
/*    1.若item是操作数, 则存入后缀表达式链表,并读取下一个元素.                        */
/*    2.若item是操作符, 判断item的优先级icp和当前位于栈顶的操作符oper的优先级isp.     */
/*    3.(1)若icp(item.value)>isp(oper.value), 令item进栈,并读取下一个元素.            */
/*      (2)若icp(item.value)<isp(oper.value), 退栈, 并将此元素存入后缀表达式链表.     */
/*      (3)若icp(item.value)=isp(oper.value), 退栈, 若退出的是'(', 则读取下一个元素.  */
/*                                                                                    */
/*====================================================================================*/
void Calculator::GetPostfix()
{ 

	Item item("#",1); 
	stack.Push(item);
	item=inlist.PopFront();
	while(!stack.IsEmpty())
	{
		if(item.flag==0)
		{
			postlist.PushBack(item);
			item=inlist.PopFront();
		}
		else
		{
			Item oper=stack.GetTop()->data; 
			if(isp(oper.value)<icp(item.value))
			{
				stack.Push(item);
				item=inlist.PopFront();
			}
			else if(isp(oper.value)>icp(item.value))
			{
				postlist.PushBack(stack.Pop());
			} 
			else
			{
				if(stack.Pop().value=="(")
					item=inlist.PopFront();
			}
		} 
	}
}

/*====================================================================================*/
/*                         通过后缀表达式计算表达式的值算法:                          */
/*                                                                                    */
/*  顺序扫描后缀表达式链表的每一项,然后根据它的类型,做如下相应操作:                   */
/*  1.如果该项是操作数,则将其压入栈中;                                                */
/*  2.如果该项是操作符<op>,则连续从栈中弹出两个操作数Y,X,形成运算指令X<op>Y;          */
/*  3.将计算结果重新压入栈中;                                                            */     
/*  4.当表达式的所有项都扫描或处理完之后,栈顶存放的就是最后的计算结果.                */
/*====================================================================================*/
float Calculator::Run()
{
	float num1,num2;
	while(!postlist.IsEmpty())
	{
		Item item=postlist.PopFront();
		if(item.flag==0) 
			result.Push(atof(item.value.c_str())); 
		else
		{
			if(result.IsEmpty())
				Error("取右操作数失败!");
			num2=result.Pop();
			if(result.IsEmpty())
				Error("取左操作数失败!");
			num1=result.Pop();
			switch(item.value[0])
			{
			case '+': result.Push(num1+num2); break;
			case '-': result.Push(num1-num2); break;
			case '*': result.Push(num1*num2); break;
			case '/':
				{
					if(num2==0.0)
					{
						result.ClearStack();
						Error("Divide by 0 !"); 
					}
					else
						result.Push(num1/num2); break;
				}
			case '%': result.Push((int)num1%(int)num2); break;
			case '^': result.Push(pow(num1,num2)); break;
			}
		}
	}
	if(result.IsEmpty())
		Error("计算失败!");
	return result.Pop();
}
#pragma endregion