中缀表达式转后缀表达式，以及后缀表达式的计算

中缀转后缀表达式

逻辑代码演示 后缀表达式计算

逻辑代码演示

先上题目链接
牛客：中缀转后缀

leetcode：后缀表达式计算

准备三个容器：

vector ret 存放最后结果stack symbol 运算符暂时存放map P 存放符号优先级 逻辑

开始遍历中缀字符串：

遇到 数字 直接存放入于输出数组 ret遇到操作符

symbol栈为空 或者 当前操作符为(，直接入栈

栈不为空 判断symbol栈顶运算符与当前运算符的优先级：

当前运算符优先级高，则当前运算符入symbol栈，随后遍历后续字符。栈顶运算符优先级高，则出栈存入ret中，再继续判断栈顶与当前运算符优先级（如栈已空则当前运算符直接入栈）。

当前运算符为 ( 直接如symbol栈。

当前运算符为 ) ，则将栈顶元素依次存入ret中，直到遇到(。此时(出栈抛弃，)也舍弃不做处理。

3.遍历结束，将symbol栈中剩余元素，依次出栈存入ret中。

4.完成中缀转后缀，ret的存放顺序即为后缀顺序。

vector infixtosuffix()
{
	string mid;
	cin >> mid;
	vector ret;//返回的字符串
	map P;//符号优先级
	P['('] = P[')'] = 0;
	P['+'] = P['-'] = 1;
	P['*'] = P['/'] = 2;
	stack symbol;//符号栈

	size_t i = 0;
	while (i < mid.size())
	{
		if (isalnum(mid[i]))
		{
			string tmp;
			while (i < mid.size() && isalnum(mid[i]))
			{
				tmp += mid[i];
				i++;
			}
			ret.push_back(tmp);//遇数字直接输出至ret
		}

		while (i < mid.size() && !symbol.empty() && P[mid[i]] <= P[symbol.top()] && mid[i] != '(')//当前符号的优先级小于等于栈顶符号则出栈
		{
			if ((mid[i] == ')') && (symbol.top() == '('))
			{
				symbol.pop();//不保留左括号
				i++;//舍弃右括号
			}
			else
			{
				ret.push_back(string(1, symbol.top()));
				symbol.pop();
			}
		}
		if (i < mid.size())
		{
			symbol.push(mid[i]);
			i++;
		}

	}
	while (!symbol.empty())
	{
		ret.push_back(string(1, symbol.top()));
		symbol.pop();
	}
	for(size_t i=0;i 
后缀表达式计算 
准备一个容器
 
stack s; 存放数字 
逻辑 
操作数入栈，遇到操作符连拿两个操作数运算（栈顶为右操作数，出栈，此时栈顶为左操作数）运算结果压栈最后的栈顶元素则为计算结果 
⚠ 注意字符与数字的转换
 
代码演示 
int reverse_poland_cal(vector& tokens)
{
	//操作数入栈，
	//遇到操作符
	//连拿两个操作数运算
	//运算结果压栈

	stack s;
	for (size_t i = 0; i < tokens.size(); ++i)
	{
		if (tokens[i] == "+"
			|| tokens[i] == "-"
			|| tokens[i] == "*"
			|| tokens[i] == "/")
		{
			int  right = s.top();
			s.pop();
			switch (tokens[i][0])//switch只判断整型，需提取字符
			{
			case '+':
				s.top() += right;
				break;
			case '-':
				s.top() -= right;
				break;
			case '*':
				s.top() *= right;
				break;
			case '/':
				s.top() /= right;
				break;
			}
		}
		else
		{
			s.push(stoi(tokens[i]));
		}
	}
	return s.top();
}
 
 
青山不改 绿水长流