中缀表达式求值 -- C++标准库的应用

基本思路

一、中缀表达式求值分两大步：

• 1、将中缀表达式转换为后缀表达式，统一形式，用空格做间隔；
• 2、后缀表达式求值。

二、中缀表达式转换为后缀表达式的思路

• 1、处理空格：输入可能不规范，统一将空格全部删除；此时运算符和括号成为数字的间隔符，方便处理。
• 2、处理单目运算符正负号±；因为它是单目运算符，运算等级要高，使用！来代表-；+号则忽略
• 3、查找运算符及间隔符
  • A、运算符不是第一个，则表达式第一个是运算数，运算数直接加入后缀表达式；
  • B、运算符是第一个，则要处理运算符：
    • B.1、第一个可定是运算符，根据优先等级，确认之前的预备运算符是否出栈，
    • B.2、将新的运算符入栈（由于这个有好几种情况需要分情况处理）
    • B.3、如果有左括号，左括号右面~标记一下，查找对应的右括号，递归调用运算符处理函数
  • C、直到中缀表达式的结尾为止。结尾处用空格来区分。
  • D、如果是第一个，而没有有效的运算符，那么就到结尾了
• 4、关于()的循环：
  • A、遇到(，则从(的下一个字符开始，递归调用中缀转换为后缀的函数。
  • B、遇到), 则跳出当前的递归层。

三、后缀表达式的求值

• 1、将后缀表达式的内容，根据类型压栈和出栈：

  如果为数值则压栈；

  如果为运算符，则将运算符对应的运算数出栈；计算结果压栈。

• 2、重复此过程，直到表达式读取结束，此时栈内有一个数，即为结果。

四、定义一个全局unorder_map，用来记录不同运算符的优先级。

程序主体：

#include<stack>
#include<string>
#include<iostream>
#include<sstream>
#include<vector>
#include<functional>
#include<unordered_map>
#include<cmath>
using std::unordered_map;	
using std::function;
using std::string;
using std::stack;
using std::cin;
using std::cout;
using std::endl;
using std::vector;

//使用类型别名，方便处理不同的类型
typedef double ValueType;
//定义基本的函数操作 加、减、乘、除及指数运算；此处使用了lambd表达式和函数
auto add = [](const ValueType &lhs, const ValueType &rhs)->ValueType { return lhs + rhs; };
auto minus = [](const ValueType &lhs, const ValueType &rhs)->ValueType { return lhs - rhs; };
auto multi = [](const ValueType &lhs, const ValueType &rhs) { return lhs * rhs; };
ValueType divide(const ValueType &lhs, const ValueType &rhs) {
	if (rhs == 0)
	{
		throw std::exception("Divisor is zero.");
		return 0;
	}
	else
		return (rhs / lhs);
}

//定义函数调用的字典，使用了可调用对象
 unordered_map<char, function<ValueType(const ValueType&,const ValueType&)>> Binops = {
	{'+',add},{'-',minus},{'*', multi},{'/',divide},{'^',std::powl}
};
//定义函数优先级的字典，其中‘！’为单目运算符负号
 //最好声明成const，但const不支持[]，因为map和set的[]操作会插入没有的值，也就是改变map和set
 unordered_map<char,int> Priority = {
	{'+',1},{'-',1},{'*', 2},{'/',2},{'^',3},{'!',4}
};
//下面四个函数是中缀转换为后缀用到的函数。
//规范中缀表达式
string deal_black(const string &line);
//中缀表达式转换成后缀表达式的函数
int change_expression(string &midExpr, string &postExpr);
//处理转换过程中运算符的函数
void deal_op(const string &opAll, size_t posk, stack<char> &opTmp, string &postExpr);
//转换过程中，处理表达式开头的函数；开头单独处理的原因是开头可能直接是正负号，表达式中正负号不可能单独存在。
void deal_begin(string &line, stack<char> &opTmp);
//后缀表达式求值的函数
int get_value(string & expression);
//求值过程中调用的处理运算的函数。
int evaluation(const char&c, stack<double> *stackPtr);
//处理运算符，此处没有括号，括号的情况已经在前处理了。
//此处运算符最多两个；两个的话，第二个是正负号。
void deal_op(const string &opAll, size_t posk, stack<char> &opTmp, string &postExpr)
{
	while (!opTmp.empty())
	{
		if (Priority[opTmp.top()] >= Priority[opAll[0]])
		{
			postExpr.push_back(' ');

			postExpr.push_back(opTmp.top());
			opTmp.pop();
		}
		else
		{
			break;
		}
	}
	opTmp.push(opAll[0]);
	if (posk == 2 && opAll[1] == '-')	//如果存在负号的话
		opTmp.push('!');	
}

//处理中序表达式中的空格
string deal_black(const string &line)
{
	string retVal;
	for (auto ch : line)
	{
		if (ch != ' ')
			retVal.push_back(ch);
	}
	return retVal;
}
//处理每个表达式的开始，开始可能有左括号，表示多重括号；可能 有正负号；不考虑其他情况，如表达式中()里面没表达式的情况。
void deal_begin(string &line, stack<char> &opTmp)
{
	string str{ "+-( " };	//表达式开头只可能有这几种运算符
	auto posOp = line.find_first_of(str);
	//没有这些符号就不用考虑了，直接处理。
	if (posOp != 0)
		return;
	auto posNum = line.find_first_not_of(str);//一个新的表达式，一定有数字
	auto opAll = line.substr(posOp, posNum - posOp);
	//查找左括号
	auto posk = opAll.find('(');

	//如果有(，只处理（前的符号，跳到（开始处理
	if (posk != string::npos)
	{
		if (opAll.find('-') != string::npos && opAll.find('-') < posk)
			opTmp.push('!');
		line = line.substr(posk);
	}
	else//没有有(，负号，跳过开始的符号开始处理。
	{
		if (opAll.find('-') != string::npos)
			opTmp.push('!');
		line = line.substr(posNum);
	}
}

int change_expression(string &midExpr, string &postExpr)
{
	/* 中缀表达式求值时，当前运算符是否求值，需要跟它后面的运算符比较：如果大于等于后面的运算符的优先级
	则可以计算，即可以加入后缀表达式；否则先记录在一个运算符的栈中，由前面的入栈条件可知，当前栈顶的运算
	符优先级最高 */
	stack<char> opTmp; //用于暂存优先级较低的运算符
	string str{ "+-*/()^ " };	//需要跳过的运算符和结尾空格
	//处理表达式开始的符号，可能为左括号或者正负号
	deal_begin(midExpr, opTmp);
	string opValid;//用于记录当前的运算符；

	while (!midExpr.empty()) 
	{
		//由于，我们的寻找符号包含空格，而表达式以空格结尾，所以此处查找比成功
		auto posOp = midExpr.find_first_of(str);
		//此时表达式前端为运算符的情况
		if (posOp == 0)
		{
			//找到第一个非运算符，即数字；数字之前的都是运算符。
			auto posNum = midExpr.find_first_not_of(str);
			//已经到达表达式的结尾了或是括号递归的结束;括号迭代结束则退出递归；空格代表表达式结束
			if (posNum == string::npos && midExpr[0] == ' ')		
				break;
			//如果为右括号，表达式扫描前进一个字符，然后退出递归（右括号前面不可能有运算符）
			if (midExpr[0] == ')')			
			{
				midExpr = midExpr.substr(1);
				break;
			}
			//提取本次扫描所有的运算符
			auto opAll = midExpr.substr(posOp, posNum - posOp);
			//找到左括号的位置
			auto posk = opAll.find('(');
			switch (posk)
			{
			//没有括号，正常处理运算符
			case string::npos: deal_op(opAll, posNum, opTmp, postExpr); 
				midExpr = midExpr.substr(posNum); break;
			//第一个就是括号，直接递归处理
			case 0: midExpr = midExpr.substr(posk + 1); change_expression(midExpr, postExpr); break;
			//其他情况，先处理括号前的运算符，再递归处理
			default: deal_op(opAll, posk, opTmp, postExpr);
				midExpr = midExpr.substr(posk + 1); change_expression(midExpr, postExpr); break;
			}
		}
		//如果表达式处理到数字，加入到后缀表达式中。
		else
		{
			//后缀表达式以空格为分隔
			if(!postExpr.empty())
				postExpr.push_back(' ');
			postExpr.append(midExpr, 0, posOp);
			//下次处理从运算符开始。
			midExpr = midExpr.substr(posOp);
		}
	}
	//如果表达式处理完了，把暂存栈中的运算符出栈，加入到后缀表达式
	while (!opTmp.empty())
	{
		postExpr.push_back(' ');
		postExpr.push_back(opTmp.top());
		opTmp.pop();
	}
	return 0;
}

int get_value(string & expression)
{

	string str;
	stack<double> ret_value;
	double number;
	std::istringstream strin(expression);
	while (strin >> str)
	{
		if (str.size() == 1 && (str[0] <'0' || str[0] >'9'))
		{
			char c = str[0];
			evaluation(c, &ret_value);
		}
			
		else
		{
			number = std::stod(str,nullptr);
			ret_value.push(number);
		}
	}
	cout << "The value of expression \"" << expression << "\" is " << ret_value.top() << endl;
	return 0;
}

int evaluation(const char&c, stack<double> *stackPtr)
{
	if (stackPtr->empty())
		return 1;
	auto second = stackPtr->top(); 
	stackPtr->pop();
	if (c == '!')
	{
		second = -second;
		stackPtr->push(second);
	}
	else
	{
		if (stackPtr->empty())
			return 1;
		auto first = stackPtr->top();
		stackPtr->pop();

		stackPtr->push(Binops[c](first, second));
	}
	return 0;
}

//入口主函数
void main()
{
	//输入表达式，输入为一行
	string line;
	getline(cin, line);
	
	//分别记录中缀和后缀表达式
	string midExpr, postExpr;
	bool isNegative = false;
	//处理表达式，使其转换为标准的中缀表达式“删除表达式内的空格，表达式以空格结尾”
	midExpr = deal_black(line);
	midExpr.push_back(' ');
	//将中缀表达式转换为后缀表达式
	change_expression(midExpr, postExpr);
	//后缀表达式求值
	get_value(postExpr);
	return 0;
}