逆波兰算法详解及应用（计算数学表达式）

1、逆波兰算法

要用C++实现一个计算器的小程序，就要使用逆波兰算法，能够根据当前用户输入的算式表达式字符串，计算出所要的结果，算式字符串可以包括加、减、乘、除和括号。例如下图实时计算字符串结果的效果：

2、使用逆波兰算法计算数学表达式

(1). 波兰式（前缀表达式）

波兰逻辑学家J.Lukasiewicz于1929年提出的表示表达式的一种方式，即二元运算符至于运算数之前的一种表达方式。

(2).中缀表达式

普通的表示表达式的一种方法，将二元运算符置于运算数中间，也是大多数情况下使用的一种方法。

(3).逆波兰式（后缀表达式）

与波兰式相反，是二元运算符置于运算数之后的一种表达方式。每一运算符都置于其运算对象之后，故称为后缀表示。

三种表达式的形象实例如下：

逆波兰式的应用——算术表达式求值

逆波兰式，也称逆波兰记法（Reverse Polish Notation）。在数据结构中，使用栈的概念完成表达式的求值操作，在计算机系统处理表达式的计算过程中，将中缀表达式转换为后缀表达式的形式进行解析转换并实施计算，这就是逆波兰算法的应用。

具体实现方法大致为：

1. 设两个栈，操作数栈和运算符栈；
2. 操作数依次入操作数栈；
3. 运算符入栈前与运算符的栈顶运算符比较优先级；
4. 优先级高于栈顶运算符，压入栈，读入下一个符号；
5. 优先级低于栈顶运算符，栈顶运算符出栈，操作数栈退出两个操作数，进行运算，结果压入操作数栈；
6. 优先级相等，左右括号相遇，栈顶运算符出栈即可；
7. 字符串表达式读完，栈顶为运算结果。

具体的实现过程如下：

详细计算的源代码如下：

//节点统计数字

int	st_StackNodeNum=0;

//链栈

template<typename Type>

struct Stack
{
	
    Type num;
	
    Stack<Type>* ptNext;
	
};

//初始化栈

template<typename Type>

void InitStack(Stack<Type>*& Node)
{
	
	Node = (Stack<Type>*)malloc(sizeof(Stack<Type>));
	
	Node->ptNext = NULL;
	
	st_StackNodeNum++;
	
}

//头插法入栈

template<typename Type>

void PushStack(Stack<Type>*& Node, Type value)
{
	
	Stack<Type>* pt = (Stack<Type>*)malloc(sizeof(Stack<Type>));
	
	pt->num = value;
	
	pt->ptNext = Node->ptNext;
	
	Node->ptNext = pt;
	
	st_StackNodeNum++;
	
}

//头插法出栈

template<typename Type>

void PopStack(Stack<Type>*& Node, Type& value)
{
	
	Stack<Type>* pt = Node->ptNext;
	
	value = pt->num;
	
	Node->ptNext = pt->ptNext;
	
	delete pt;
	
	st_StackNodeNum--;
	
}

//头插法出栈

template<typename Type>

void DestroyStack(Stack<Type>*& Node)
{
	
	if(Node->ptNext == NULL)
	{
		
		delete Node;
		
		Node=NULL;
		
		st_StackNodeNum--;
		
	}
	
}

//判断栈是否为空，除去没有存数据的首个节点外

template<typename Type>

bool IsStackEmpty(Stack<Type>* Node)
{
	
	return Node->ptNext == NULL;
	
}

//获取栈顶部节点的数据

template<typename Type>

Type GetStackTopValue(Stack<Type>* Node)
{
	
	if(Node->ptNext !=NULL){return Node->ptNext->num;}else{return 0;}
	
}


void	CalValue(Stack<double> *&ptNumStack,Stack<char> *&ptOperatorStack)
{
	
    double NumberLeft, NumberRight, NumberResult;
	
    char Operator;
	
	//将栈顶的两个数字和一个操作符进行出栈操作
	
    PopStack(ptNumStack, NumberRight);
	
    PopStack(ptNumStack, NumberLeft);
	
    PopStack(ptOperatorStack, Operator);
    
	//对出栈的两个数字和一个操作符进行计算
	
    if (Operator == '+')NumberResult = NumberLeft + NumberRight;
	
    if (Operator == '-')NumberResult = NumberLeft - NumberRight;
	
    if (Operator == '*')NumberResult = NumberLeft * NumberRight;
	
    if (Operator == '/')NumberResult = NumberLeft / NumberRight;
	
	//将计算后的结果继续押入栈中
	
    PushStack(ptNumStack, NumberResult);
	
}

//逆波兰算法实现

double	Polish(char *String, int len)
{
	
    Stack<double> *ptNumStack;
	
    Stack<char> *ptOperatorStack;
	
	//初始栈，最主要产生一个默认的节点
	
    InitStack(ptNumStack);
	
	InitStack(ptOperatorStack);
	
	//逐字符读取字符串的游标位置
	
    int index = 0;
	
	//逐字符读取字符串
	
    while(!IsStackEmpty(ptOperatorStack) || index<len)
	{
		
        //当前游标位置小于字符串长度时，逐个获取数字和运算符号并进行运算；否则做收尾工作
		
        if(index<len)
		{
			
            //如果当前游标位置为数字，则说明这里是我们需要读取数字的开始位置
			
            if((String[index] >= '0' && String[index] <= '9') || String[index]=='.')
			{
				
				//将此后的数字区域读取到临时字符串
				
				char szTempNum[100]="";
				
				int iPos=0;
				
				//循环取得数字，当遇到第一个不是数字或小数点的字符
				
				for(int i=index;i<len;i++)
				{
					
					if((String[i] >= '0' && String[i] <= '9') || String[i]=='.')
					{
						
						szTempNum[iPos++]=String[i];
						
						index++;
						
					}
					else
					{
						
						break;
						
					}
					
				}
				
				szTempNum[iPos]='\0';
				
				//获取到我们需要的数字，并将数字保存到栈中
				
				double tempNumber=atof(szTempNum);
				
				PushStack(ptNumStack, tempNumber);
				
            }
            else 
			{
				
				//如果当前字符串为运算符，则根据运行符的种类进行判断

                if (String[index] == '(' || (GetStackTopValue(ptOperatorStack) == '(' && String[index] != ')') || IsStackEmpty(ptOperatorStack))
				{
					
					//遇到以上情况，则直接将运行符保存的符号栈中
					
                    PushStack(ptOperatorStack, String[index++]);

                }
                else if (String[index] == '+' || String[index] == '-')
				{
					
					//如果遇到加、减号，就把此前已入栈的算式进行计算，并将结果结果和符号重新入栈

                    while (GetStackTopValue(ptOperatorStack) != '(' && !IsStackEmpty(ptOperatorStack))
					{

                        CalValue(ptNumStack, ptOperatorStack);

                    }

                    PushStack(ptOperatorStack, String[index++]);

                }
                else if (String[index] == '*' || String[index] == '/')				
				{

                    //如果遇到乘、除号，则把之前所有乘、除相关的算式进行计算，并将结果结果和符号重新入栈

                    while (GetStackTopValue(ptOperatorStack) == '*' || GetStackTopValue(ptOperatorStack) == '/')
					{

                        CalValue(ptNumStack, ptOperatorStack);

                    }

                    PushStack(ptOperatorStack, String[index++]);

                }
                else if (String[index] == ')')
				{

					//当遇到有括号，则把所有括号对内的算式计算完毕，右括号无需入栈

					while(GetStackTopValue(ptOperatorStack) != '(') 
					{
						
						//当栈为空时无需进行计算跳出循环

						if(IsStackEmpty(ptOperatorStack))break;

						CalValue(ptNumStack, ptOperatorStack);

					}

					//当计算完所有括号内容的算式，弹出对应的左括号

					char tempBracket;

					PopStack(ptOperatorStack, tempBracket);

					index++;
					
                }

            }

        }
        else
		{
			
			//遍历完字符串所有字符后，只需对还未空的运算符栈进行逐步计算
			
			CalValue(ptNumStack, ptOperatorStack);
			
        }
		
    }
	
	//最后栈顶（根节点的下一个节点）的数据就是表达式的结果
	
	double NumberValue=0;
	
	PopStack(ptNumStack,NumberValue);
	
	//在删除所有子节点后销毁栈的根节点
	
	DestroyStack(ptNumStack);
	
	DestroyStack(ptOperatorStack);
	
	//返回计算的结果
	
    return NumberValue;
	
}

3、源码下载

该源码可以在VS2010和VC6.0中无差异运行，因此就上传了两个版本的源码，方便运行。

3.1、VS2010源码下载

CSDN下载地址：Calculator20241207-15-vs2010.rar

3.2、VC6.0源码下载

CSDN下载地址：Calculator20241207-15-vc6.0.rar