利用堆栈进行表达式求值

基本策略：将中缀表达式转换为后缀表达式，然后求值
中缀表达式转换为后缀表达式的流程：
从头到尾读取中缀表达式的每个对象，对不同的对象按不同的情况处理
(1) 运算数：直接输出
(2) 左括号：压入堆栈，入栈前左括号的优先级最高, 入栈之后其优先级降到最低
(3) 右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）
(4) 运算符：
    [1] 若优先级大于栈顶运算符时，则把它压栈
    [2] 若优先级小于栈顶运算符时，将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到该运算符大于栈顶运算符为止，然后将该运算符压栈；
(4) 若各对象处理完毕，则把堆栈中存留的运算符一并输出
 

#pragma once
#include <stdio.h>

/*
表达式运算, 实现基本的表达式求值, 支持运算符： +, -, *, /, (, )
*/

class CExpressOperation
{
public:
	CExpressOperation();
	~CExpressOperation();

	// 输入一个中缀表达式，求出结果
	bool CalculateValue(char* infix, double& result);

private:
	// 运算符以及优先级
	struct sOperator
	{
		char type;		// 存储运算符
		char wight;		// 运算符优先级
	};
	// 定义堆栈
	struct sNode
	{
		char	type; // 0 运算数, 非零表示运算符
		double	val;  // type为0时, val存储运算数
		sOperator sOpr;
		sNode* pNext; // 当首节点的pNext为NULL时候, 代表堆栈是空的
		sNode()
		{
			type = 0;
			pNext = NULL;
		}
	};

	// 将字符中缀表达式转换为链表格式
	bool InfixToLink(char* infix, sNode& link);
	// 中缀表达式转换为后缀表达式
	bool InfixToSuffix(sNode& lkInfix, sNode& lkSuffix);
	// 后缀表达式求值
	bool CalSuffix(sNode& lkSuffix, double& result);
	// 删除堆栈
	void DelStack(sNode& stack);
	// 入栈
	void StackPush(sNode& stack, sNode* pNode);
	// 出栈
	bool StackPop(sNode& stack, sNode& node);
	// 栈是否为空
	bool IsStackEmpty(sNode& stack);
	// 在链表末端插入
	void LinkAddTail(sNode& link, sNode* pNode);
	// 顺序打印
	void LinkPrint(sNode& link);
};

#include "ExpressOperation.h"
#include <string.h>
#include <ctype.h>
#include <math.h>

#define Opr_Add		2
#define Opr_Sub		2
#define Opr_Mul		3
#define Opr_Div		3
#define Opr_Left		4	// 左括号
#define Opr_Right		4	// 右括号
#define Opr_SLeft		1	// 左括号入栈后优先级降为最低

CExpressOperation::CExpressOperation()
{
}

CExpressOperation::~CExpressOperation()
{
}

// 输入一个中缀表达式，求出结果
bool CExpressOperation::CalculateValue(char* infix, double& result)
{
	sNode lkSuffix;
	sNode lkInfix;
	if (!InfixToLink(infix, lkInfix))
	{
		DelStack(lkInfix);
		return false;
	}
	if (!InfixToSuffix(lkInfix, lkSuffix))
	{
		DelStack(lkInfix);
		DelStack(lkSuffix);
		return false;
	}
	bool bRet = CalSuffix(lkSuffix, result);
	DelStack(lkInfix);
	DelStack(lkSuffix);
	return bRet;
}

// 将字符中缀表达式转换为链表格式
bool CExpressOperation::InfixToLink(char* infix, sNode& link)
{
	char szBuff[50];
	int iE = 0;
	int iB = 0;
	double tVal = 0;
	int iLen = strlen(infix);
	sNode* pNode;
	sOperator sOpr;

	while (iE < iLen)
	{
		iB = 0;
		memset(szBuff, 0, sizeof(szBuff));
		while (iE < iLen)
		{
			if (isdigit(infix[iE]) || infix[iE] == '.')
			{
				szBuff[iB++] = infix[iE++];
				continue;
			}
			if (infix[iE] == ' ' || infix[iE] == '\t')
			{
				iE++;
				continue;
			}
			switch (infix[iE])
			{
			case '+':
				sOpr.type = '+';
				sOpr.wight = Opr_Add;
				break;
			case '-':
				sOpr.type = '-';
				sOpr.wight = Opr_Sub;
				break;
			case '*':
				sOpr.type = '*';
				sOpr.wight = Opr_Mul;
				break;
			case '/':
				sOpr.type = '/';
				sOpr.wight = Opr_Div;
				break;
			case '(':
				sOpr.type = '(';
				sOpr.wight = Opr_Left;
				break;
			case ')':
				sOpr.type = ')';
				sOpr.wight = Opr_Right;
				break;
			default:
				return false;	// 遇到非法字符
				break;
			}
			if (iB > 0)
			{
				tVal = atof(szBuff);
				pNode = new sNode();
				pNode->type = 0;
				pNode->val = tVal;
				LinkAddTail(link, pNode);
				iB = 0;
			}
			pNode = new sNode();
			pNode->type = 1;
			pNode->sOpr = sOpr;
			LinkAddTail(link, pNode);
			iE++;
			break;
		}

		if (iB > 0)
		{
			tVal = atof(szBuff);
			pNode = new sNode();
			pNode->type = 0;
			pNode->val = tVal;
			LinkAddTail(link, pNode);
			iB = 0;
		}
	}
	return true;
}

// 中缀表达式转换为后缀表达式
bool CExpressOperation::InfixToSuffix(sNode& lkInfix, sNode& lkSuffix)
{
	sNode* pSuf;
	sNode* pInf;
	sNode skOpr;
	sNode skNode;
	pInf = lkInfix.pNext;
	while (pInf)
	{
		if (pInf->type == 0) // 运算数：直接输出
		{
			pSuf = new sNode();
			*pSuf = *pInf;
			pSuf->pNext = NULL;
			LinkAddTail(lkSuffix, pSuf);
		}
		else
		{
			if (pInf->sOpr.type == '(')
			{ // 左括号：压入堆栈
				pSuf = new sNode();
				*pSuf = *pInf;
				pSuf->sOpr.wight = Opr_SLeft;
				StackPush(skOpr, pSuf);
			}
			else if (pInf->sOpr.type == ')')
			{ // 右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）
				while (!IsStackEmpty(skOpr))
				{
					StackPop(skOpr, skNode);
					if (skNode.sOpr.type == '(')
						break;
					else
					{
						pSuf = new sNode();
						*pSuf = skNode;
						LinkAddTail(lkSuffix, pSuf);
					}
				}
			}
			else
			{
				bool bPush = false;
				while (!IsStackEmpty(skOpr))
				{
					sOperator sOpr = skOpr.pNext->sOpr;
					if (pInf->sOpr.wight > sOpr.wight) //[1] 若优先级大于栈顶运算符时，则把它压栈
					{
						pSuf = new sNode();
						*pSuf = *pInf;
						StackPush(skOpr, pSuf);
						bPush = true;
						break;
					}
					else
					{// 否则栈顶元素弹出
						StackPop(skOpr, skNode);
						pSuf = new sNode();
						*pSuf = skNode;
						LinkAddTail(lkSuffix, pSuf);
					}
				}
				if (!bPush)
				{// 如果栈为空, 则压栈
					pSuf = new sNode();
					*pSuf = *pInf;
					StackPush(skOpr, pSuf);
				}
			}
		}
		pInf = pInf->pNext;
	}

	// 处理结束后, 还需要检查堆栈的元素, 不为空则全部弹出
	while (!IsStackEmpty(skOpr))
	{
		StackPop(skOpr, skNode);
		if (skNode.sOpr.type != '(' && skNode.sOpr.type != ')')
		{
			pSuf = new sNode();
			*pSuf = skNode;
			LinkAddTail(lkSuffix, pSuf);
		}
	}

	DelStack(skOpr);
	return true;
}
// 后缀表达式求值
bool CExpressOperation::CalSuffix(sNode& lkSuffix, double& result)
{
	// 遇到数值就压栈
	// 遇到运算符, 就从堆栈取出两个数值计算, 将结果压栈
	sNode skVal;
	sNode* pSuf;
	sNode* pSK;
	sNode top1, top2;

	pSuf = lkSuffix.pNext;
	if (NULL == pSuf)
		return 0;

	while (pSuf)
	{
		if (pSuf->type == 0)
		{// 遇到数值就压栈
			pSK = new sNode();
			*pSK = *pSuf;
			StackPush(skVal, pSK);
		}
		else
		{// 遇到运算符, 就从堆栈取出两个数值计算, 将结果压栈
			if (!StackPop(skVal, top1))
				return false;	// 表达式错误
			if (!StackPop(skVal, top2))
				return false;	// 表达式错误
			pSK = new sNode();
			pSK->type = 0;
			switch (pSuf->sOpr.type)
			{
			case '+':
				pSK->val = top2.val + top1.val;
				break;
			case '-':
				pSK->val = top2.val - top1.val;
				break;
			case '*':
				pSK->val = top2.val * top1.val;
				break;
			case '/':
				pSK->val = top2.val / top1.val;
				break;
			default:
				delete pSK;
				DelStack(skVal);
				return false;
				break;
			}
			StackPush(skVal, pSK);
		}
		pSuf = pSuf->pNext;
	}

	if (!StackPop(skVal, top1))
	{
		DelStack(skVal);
		return false;
	}
	result = top1.val;
	DelStack(skVal);
	return true;
}
// 删除堆栈
void CExpressOperation::DelStack(sNode& stack)
{
	sNode* p;
	while (stack.pNext)
	{
		p = stack.pNext;
		stack.pNext = p->pNext;
		delete p;
	}
}

// 入栈
void CExpressOperation::StackPush(sNode& stack, sNode* pNode)
{
	if (NULL == pNode) return;
	pNode->pNext = stack.pNext;
	stack.pNext = pNode;
}
// 出栈
bool CExpressOperation::StackPop(sNode& stack, sNode& node)
{
	if (stack.pNext == NULL) return false;
	sNode* pN = stack.pNext;
	stack.pNext = pN->pNext;
	node = *pN;
	delete pN;
	return true;
}
// 栈是否为空
bool CExpressOperation::IsStackEmpty(sNode& stack)
{
	if (NULL == stack.pNext)
		return true;
	else
		return false;
}
// 在链表末端插入
void CExpressOperation::LinkAddTail(sNode& link, sNode* pNode)
{
	if (NULL == pNode) return;
	sNode* pTail = &link;
	while (pTail->pNext)
	{
		pTail = pTail->pNext;
	}
	pTail->pNext = pNode;
	pNode->pNext = NULL;
}

// 顺序打印
void CExpressOperation::LinkPrint(sNode& link)
{
	sNode* pNode = link.pNext;
	while (pNode)
	{
		if (pNode->type == 0)
			printf("%0.3f ", pNode->val);
		else
		{
			printf("%c ", pNode->sOpr.type);
		}
		pNode = pNode->pNext;
	}
	printf("\n");
}