中缀表达式转后缀表达式

// 1.利用map将不同字符串按其优先顺序映射为不同等级「并且保证“(”为最低等级」
 如：map M;
 M[“+”]=1;M[“*”]=2;
// 2.遇到“”，入栈
// 3.遇到“”，循环输出栈元素，直到遇到“”，并将“”出栈（但不输出）
// 4.遇到digit，输出
// 5.遇到运算符，循环输出栈中>=此运算符的元素
// 6.读取结束后，将栈清空（输出）

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int MAXSIZE = 1e3 + 5;
template   //自定义栈
class MyStack
{
private:
	T data[MAXSIZE];
	int Top;
public:
	MyStack() :Top(0){}
	bool empty(){ return Top == 0; }
	void push(T t){ data[Top++] = t; }
	void pop(){ Top--; }
	T top(){ return data[Top - 1]; }
};
template   //自定义队
class MyQueue
{
private:
	T data[MAXSIZE];
	int f, r;
	int len;
public:
	MyQueue() :f(0), r(0), len(0){}
	bool empty(){ return size == 0; }
	void push(T t){ data[r] = t; r = (r + 1) % MAXSIZE; len++; }
	void pop(){ f = (f + 1) % MAXSIZE; len--; }
	int size(){ return len; }
};
vector vstr;	//存储处理后的标准运算式（中缀表达串组）
map MAP;	//标记符号级别
int finddigit(string &str, int i)
{
	i++;
	for (;;)
	{
		if ((str[i] <= '9'&&str[i] >= '0') || str[i] == '.')
			i++;
		else return i;
	}
}
void read() //读取一行（包括小数 多位数）并存入vstr数组
{
	string str;
	getline(cin, str);
	for (int i = 0; i < str.length(); i++)
	{
		if (str[i] == '-' || str[i] == '/' || str[i] == '*' || str[i] == '+')
		{
			if (str[i] == '+' || str[i] == '-')
			{
				if (i == 0 || str[i - 1] == '(')//符号 并非运算符
				{
					string temp;
					int n = finddigit(str, i);
					if (str[i] == '+')
					{
						temp = str.substr(i + 1, n - i - 1);
						vstr.push_back(temp);
					}
					else if (str[i] == '-')
					{
						temp = str.substr(i, n - i);
						vstr.push_back(temp);
					}
					i = n - 1;
				}
				else //运算符
				{
					string t;
					t += str[i];
					vstr.push_back(t);
				}
			}
			else// '* /'
			{
				string t;
				t += str[i];
				vstr.push_back(t);
			}
		}
		else if (str[i] == '(' || str[i] == ')')
		{
			string t;
			t += str[i];
			vstr.push_back(t);
		}
		else
		{
			string temp; int n = finddigit(str, i);
			temp = str.substr(i, n - i);
			vstr.push_back(temp);
			i = n - 1;
		}
	}
}
int main()
{
	// 令括号为最小级 方便操作
	MAP["("] = 0;
	MAP["+"] = 1;
	MAP["-"] = 1;
	MAP["*"] = 2;
	MAP["/"] = 2;
	read();
	MyStack sta;	//处理表达式转换
	MyQueue que;	//存储后缀表达式
	for (auto elem : vstr)
	{
		// '('时就入栈
		if (elem == "(")sta.push(elem);
		// ')'时弹出直到'('出现
		else if (elem == ")")
		{
			while (sta.top() != "(")
			{
				que.push(sta.top());
				sta.pop();
			}
			sta.pop();	//弹出左括号
		}
		// 运算符时弹出符号 直到级别小于elem
		else if (elem == "+" || elem == "-" || elem == "*" || elem == "/")
		{
			//保证栈不能为空
			while (!sta.empty()&&MAP[sta.top()] >= MAP[elem])
			{
				que.push(sta.top());
				sta.pop();
			}
			sta.push(elem);
		}
		// 数字直接弹出
		else
		{
			que.push(elem);
		}
	}
	// 清空栈
	while (!sta.empty())
	{
		que.push(sta.top());
		sta.pop();
	}
	//此刻que队列已存好后缀表达式
}

中缀表达式转后缀表达式

C/C++/C#相关栏目本月热门文章