1-3 表达式转换 (25分) HBU-DS 实验

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。

输入格式:

输入在一行中给出不含空格的中缀表达式，可包含+、-、*、\以及左右括号()，表达式不超过20个字符。

输出格式:

在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。

输入样例:

2+3*(7-4)+8/4

输出样例:

2 3 7 4 - * + 8 4 / +

~

依旧是比较坎坷的一道题。

思路

先不考虑细节，首先，大致思路是：如果遇到数字就直接输出，如果遇到符号，判断他是不是比现在栈顶的符号优先级高，如果高的话就入栈，低的话（栈里的元素优先级高），就把栈里所有比他高的符号都出栈（如果优先级相同也出栈，因为相同优先级从左至右运算）。所有应该出栈的元素出栈之后，就把当前元素入栈。

注意，‘(’ 这个优先级在栈里是最低的，而在栈外最高。

好的，现在来说细节。我遇到的问题有三个：格式，小数+非单位数（我刚开始按照整数写的，一个都过去），数字带着+ - 号。

格式：就设置一个cnt，如果第一次输出数字就直接数字，否则就空格+数字。

小数+非单位数：判断下一个是不是小数点或者数字，如果是就输出，再判断

正负号：出现正负号的地方，无非两个：这个字符串的第一个位置，以及左括号之后。设置一个last（char），存上上一个字符，每次循环先判断last是不是左括号，如果是就：如果是负号就输出符号然后continue，正号直接continue；

为了统一操作，将last的初始值设置为了左括号，以此作为开头是+ -号的补充。

代码

#include <iostream> #include <string> using namespace std; int main() { char S[25]; int top = -1; string str; cin >> str; S[++top] = '('; char last = '('; int cnt = -1; for (auto it = str.begin(); it != str.end(); it++) { if (last == '(') { last = *it; if (*it == '+') continue; if (*it == '-') { cout << "-"; continue; } } last = *it; if (*it <= '9' && *it >= '0') { if (++cnt == 0) cout << *it; else cout << " " << *it; while ((it + 1) != str.end() && (*(it + 1) <= '9' && *(it + 1) >= '0' || *(it + 1) == '.')) { it++; cout << *it; } } else if (*it == '+' || *it == '-') { if (S[top] == '(') S[++top] = *it; else { while (S[top] == '+' || S[top] == '-' || S[top] == '*' || S[top] == '/') cout << " " << S[top--]; S[++top] = *it; } } else if (*it == '*' || *it == '/') { if (S[top] == '(' || S[top] == '+' || S[top] == '-') S[++top] = *it; else { while (S[top] == '*' || S[top] == '/') cout << " " << S[top--]; S[++top] = *it; } } else if (*it == '(') S[++top] = *it; else if (*it == ')') { while (S[top] != '(') { cout << " " << S[top--]; } top--; } } while (S[top] != '(') { cout << " " << S[top--]; } }