中綴表達式求值 -- 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;
}