一起学习交流~

中缀表达式和后缀表达式

算法 laomuji 11个月前 (10-26) 386次浏览 已收录 0个评论

一、用途

比如要得到5+2*(1+6)-8/2的运算结果.

5+2*(1+6)-8/2 是中缀表达式,运算符在中间,

但对于计算机来说,这样的计算太复杂了,需要转换为后缀表达式

5,2,1,6,+,x,+,8,2,/,-

二、原理

中缀表达式转后缀表达式
1.遇到数字直接输出
2.遇到符号
2.1 栈为空或栈顶为(直接入栈,直接入栈
2.2 符号优先级比栈顶运算符高,入栈
2.3 若符号优先级小于等于栈顶,栈顶出栈输出(直到遇到大于优先级的栈顶),将当前符号入栈
3.遇到括号
3.1遇到(直接入栈
3.2遇到)出栈并输出直到遇到(
4.栈剩下的元素直接出栈并输出

中缀转后缀:
(1)5
后缀表达式:5
栈:
(2)+
后缀表达式:5
栈:+
(3)2
后缀表达式:5,2
栈:+
(4)x
后缀表达式:5,2
栈:+,x
(5)(
后缀表达式:5,2
栈:+,x,(
(6)1
后缀表达式:5,2,1
栈:+,x,(
(7)+
后缀表达式:5,2,1
栈:+,x,(,+
(8)6
后缀表达式:5,2,1,6
栈:+,x,(,+
(9))
后缀表达式:5,2,1,6,+
栈:+,x
(10)-
后缀表达式:5,2,1,6,+,x,+
栈:-
(11)8
后缀表达式:5,2,1,6,+,x,+,8
栈:-
(12)/
后缀表达式:5,2,1,6,+,x,+,8
栈:-,/
(13)2
后缀表达式:5,2,1,6,+,x,+,8,2
栈:-,/
(14)
后缀表达式:5,2,1,6,+,x,+,8,2,/,-

后缀表达式计算:
1.遇到数字直接入栈
2.遇到符号,栈顶和次栈顶出栈,次栈顶 符号 栈顶 进行运算,将结果入栈

计算后缀:

遇到:5,2,1,6
入栈:5,2,1,6
栈:5,2,1,6

遇到+,出栈6,1,运算1+6=7,入栈7
栈:5,2,7

遇到x,出栈7,2,运算2×7=14,入栈14
栈:5,14

遇到+,出栈14,5,运算5+14=19,入栈19
栈:19

遇到:8,2
入栈:8,2
栈:19,8,2


遇到/,出栈2,8,运算8/2=4,入栈4
栈:19,4


遇到-,出栈4,19,运算19-4=15,入栈15
栈15

最后只剩下一个15,直接出栈,就是结果

三、代码

#include<iostream>
#include<vector>
#include<stack>
#include<string>
#include<sstream>
using namespace std;

class MathCalc
{
public:
	//计算中缀表达式
	double initExpression(string expression)
	{
		//把字符串分割为中缀表达式
		vector<string>infixVector = splitExpression(expression);

		//把中缀表达式分割为后缀表达式
		vector<string>suffixVector = infixToSuffix(infixVector);
		cout << "转换为后缀表达式:";
		for (size_t i = 0; i < suffixVector.size(); i++)
		{
			cout << suffixVector[i] << " ";
		}
		cout << endl;
		//计算后缀表达式
		return calculateSuffix(suffixVector);
	}
private:
	//分离表达式的数字和符号
	vector<string> splitExpression(string expression)
	{
		vector<string>rvec;
		rvec.push_back(string());

		//循环表达式,判断每一位是数字还是符号
		for (unsigned int i = 0; i < expression.size(); i++)
		{
			//获取当前字符
			char ch = expression[i];
			if ((ch >= '0' && ch <= '9') || ch == '.')
			{
				//如果这个表达式是数字,叠加(用于处理有多位的数字)
				rvec[rvec.size() - 1].push_back(ch);
			}
			else if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')')
			{
				//如果正在使用的string为空,表示可以直接使用
				//如果不为空,就表示上次是数字,需要终止使用
				if(rvec[rvec.size() - 1].size())rvec.push_back(string());

				//把符号放进去,因为符号只有一个,不用叠加
				rvec[rvec.size() - 1].push_back(ch);

				//再创建一个string,存放数字
				rvec.push_back(string());
			}
			else
			{
				throw exception("表达式有误!");
				exit(1);
			}
		}
		return rvec;
	}

	//中缀转后缀表达式
	vector<string> infixToSuffix(vector<string>& infix)
	{
		vector<string>rvec;
		stack<string>expressionStack;
		//循环处理中缀表达式数组
		for (unsigned int i = 0; i < infix.size(); i++)
		{
			string str = infix[i];
			string top;//存放栈顶元素
			if (str[0] >= '0' && str[0] <= '9')
			{
				//数字直接输出
				rvec.push_back(str);
			}
			else if (str == "+" || str == "-" || str == "*" || str == "/")
			{
				//栈为空或栈顶为(直接入栈,直接入栈
				if (expressionStack.size() == 0 || expressionStack.top() == "(")
				{
					expressionStack.push(str);
					continue;
				}
				//符号优先级比栈顶运算符高,入栈
				top = expressionStack.top();//获取栈顶元素
				if ((top == "(" || top == "+" || top == "-") && (str == "*" || str == "/"))
				{
					expressionStack.push(str);
					continue;
				}
				//对栈顶循环出栈
				while (expressionStack.size())
				{
					top = expressionStack.top();
					if ((str == "+" || str == "-") || (top == "*" || top == "/"))
					{
						//+和-是最小的,所以当前符号一定小于栈顶
						//str不为+-,那么一定是x/,x/不可能小于栈顶,那么必须栈顶也为x或/才相等
						rvec.push_back(top);
						expressionStack.pop();
						continue;
					}
					break;
				}
				expressionStack.push(str);

			}
			else if (str == "(" || str == ")")
			{

				if (str == "(")
				{
					expressionStack.push(str);//遇到(直接入栈
				}
				else
				{
					//遇到),循环出栈直到遇到(终止
					while (expressionStack.size())
					{
						top = expressionStack.top();
						expressionStack.pop();
						if (top == "(")break;
						else rvec.push_back(top);
					}
				}
			}
		}
		//把剩下的符号出栈
		while (expressionStack.size())
		{
			rvec.push_back(expressionStack.top());
			expressionStack.pop();
		}
		return rvec;
	}
	//计算后缀表达式
	double calculateSuffix(vector<string>&suffix)
	{
		stack<string>suffixStack;
		double num = 0;
		//循环后缀表达式
		for (unsigned int  i = 0; i < suffix.size(); i++)
		{
			string str = suffix[i];
			if (str[0] >= '0' && str[0] <= '9')
			{	
				//数字直接入栈
				suffixStack.push(str);
			}
			else
			{
				//符号先把两个数字出栈
				double top1 = strToDouble(suffixStack.top());
				suffixStack.pop();
				double top2 = strToDouble(suffixStack.top());
				suffixStack.pop();
				double res = 0.0;
				if (str == "+") res = (top2 + top1);
				else if (str == "-")res = (top2 - top1);
				else if (str == "*")res = (top2 * top1);
				else if (str == "/")res = (top2 / top1);
				suffixStack.push(to_string(res));
			}
		}
		num = strToDouble(suffixStack.top());
		suffixStack.pop();
		return num;
	}

	//把string转为double
	double strToDouble(string str)
	{
		istringstream iss(str);
		double rnum;
		iss >> rnum;
		return rnum;
	}
};

int main()
{
	MathCalc calc;
	cout << calc.initExpression("5+2*(1+6)-8/2") << endl;
	cout << calc.initExpression("5+2.15*(1.2+6)-80.8/20.2") << endl;
	return 0;
}
喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论