PTA 7-1 表达式转换——表达式树

PTA 7-1 表达式转换——表达式树

7-1 表达式转换（25 分）

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

输入格式:

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

输出格式:

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

输入样例:

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

输出样例:

2 3 7 4 - * + 8 4 / +

思路：直接套表达式树，注意检查一下能否表示两位以上的数字以及负数

#include #include using namespace std;int flag;void output(char *str, int l, int r) { bool exist = false; int cnt = 0, pos1 = -1, pos2 = -1; for (int i = l; i <= r; i++) { switch (str[i]) { case '(': cnt++; exist = true; break; case ')': cnt--; exist = true; break; case '*': case '/': exist = true; if (!cnt) pos2 = i; break; case '+': case '-': if (i != l) { exist = true; if (!cnt) pos1 = i; } break; } } if (!exist) { if (flag++) printf(" "); for (int i = (str[l] == '+' ? l + 1 : l); i <= r; i++) printf("%c", str[i]); return; } if (pos1 == -1) pos1 = pos2; if (pos1 == -1) { output(str, l + 1, r - 1); return; } output(str, l, pos1 - 1); output(str, pos1 + 1, r); if (flag++) printf(" "); printf("%c", str[pos1]);}int main() { char str[100]; scanf("%s", str + 1); int n = strlen(str + 1); flag = 0; output(str, 1, n); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。