PTA-7-20表达式转换（中缀转后缀，带括号，负数，小数转换）

本题考点：中缀表达式转后缀表达式。难点：

1. 带有⼩数的数字2. 数字可能带有正负号

题⽬描述：

算术表达式有前缀表⽰法、中缀表⽰法和后缀表⽰法等形式。⽇常使⽤的算术表达式是采⽤中缀表⽰法，即⼆元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。本题的测试点如下：

输⼊2+3*(7-4)+8/41314+25.5*12-2*(+3)123

输出

说明

2 3 7 4 - * + 8 4 / +正常测试6种运算符

1314 25.5 12 * +运算数超过1位整数且有⾮整数出现-2 3 *123

运算数前有正负号只有⼀个数字

((2+3)*4-(8+2))/52 3 + 4 * 8 2 + - 5 /嵌套括号

我们先来说明中缀转后缀的思路：1. 中缀转后缀

建⽴⼀个操作符栈，⽤以临时存放操作符，建⽴⼀个数组或者队列，⽤以存放后缀表达式

从左到右扫描中缀表达式，如果碰到操作数，就把操作数加⼊到后缀表达式中如果碰到操作符 op，就把其优先级和操作符栈顶操作符优先级⽐较

如果 op 的优先级⾼于栈顶，就压⼊操作符栈（trick：初始化操作符栈时候增加⼀个 # 运算符为最低）

如果低于或者等于栈顶，就将操作符栈的操作符不断弹出到后缀表达式中，直到 op 的优先级⾼于栈顶操作符重复直到中缀表达式扫描完毕，如果操作符栈中仍然有元素，则依次弹出放到后缀表达式中括号的处理⽅式

将左括号的优先级设置为⽐ + - 更低，但是直接插⼊

如果遇到右括号，那么直接从操作符栈中弹出到后缀表达式中，直到遇到左括号

2. 后缀表达式的计算

从左到右扫描后缀表达式，如果是操作数，就压⼊栈，如果是操作符，就连续弹出两个操作数，（后弹出的是第⼀操作数）然后进⾏操作符的操作，直到后缀表达式扫描完毕，这个时候结果栈中只剩⼀个元素，即为运算的结果

那么回归到本题，本题只要我们先把中缀转成后缀，所以我们可以先不计算出每个位置具体数值，⽽是⽤字符串保存下来即可。完整代码和注释如下：

/*

Author： Veeupup */

#include #include #include #include #include

using namespace std;

vector ans;map priority;

string operators = \"+-*/()\"; // 保存所有的计算符号

void trans(string str) {

stack ops; ops.push('#'); string tempStr;

for (int i = 0; i < str.size(); i++) { // 检查是否是带符号的数字

// 1. 带正负号且前⼀个字符为运算符（i=0时直接带正负号的也是数字） // 2. 当前字符为数字

if( ((str[i] == '-' || str[i] == '+') && (i == 0 || string(\"+-/*(\").find(str[i-1])!=string::npos)) || isdigit(str[i]) ) { // 把操作数加⼊到后缀式中

// 如果是正号就不⽤加⼊，负号或者数字本⾝都要加⼊

tempStr = str[i] != '+' ? str.substr(i, 1) : \"\";

while (i + 1 < str.size() && operators.find(str[i+1]) == string::npos) {

tempStr += str[++i]; }

ans.push_back(tempStr); }else { // 出现操作符 if(str[i] == '(')

ops.push(str[i]); else if(str[i] == ')') {

while (ops.top() != '(') {

ans.push_back(string(1, ops.top())); ops.pop(); }

ops.pop(); }else {

while (priority[str[i]] <= priority[ops.top()]) {

ans.push_back(string(1, ops.top())); ops.pop(); }

ops.push(str[i]); } } }

while (ops.size() > 1) {

ans.push_back(string(1, ops.top())); ops.pop(); }}

int main(){

priority['*'] = priority['/'] = 3; priority['+'] = priority['-'] = 2; priority['('] = 1; priority['#'] = 0; string str;

getline(cin, str); trans(str);

for (int i = 0; i < ans.size(); i++) cout << (i ? \" \" : \"\") << ans[i]; return 0;}

路漫漫其修远兮，吾将上下⽽求索。