7-6 表达式转换（25 分）
算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。 输入格式:
输入在一行中给出不含空格的中缀表达式，可包含+、-、*、\以及左右括号()，表达式不超过20个字符。 输出格式:
在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。 输入样例:
2+3*(7-4)+8/4
输出样例:
2 3 7 4 - * + 8 4 / +
思路 中缀转后缀 的原则
1.遇到操作数，直接输出； 2.栈为空时，遇到运算符，入栈； 3.遇到左括号，将其入栈； 4.遇到右括号，执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出； 5.遇到其他运算符’+”-”*”/’时，弹出所有优先级大于或等于该运算符的栈顶元素，然后将该运算符入栈； 6.最终将栈中的元素依次出栈，输出。 经过上面的步骤，得到的输出既是转换得到的后缀表达式。 举例：a+b*c+(d*e+f)g ———> abc+de*f+g*+
然后 有几个 坑点 0.操作数 不一定是一位的 比如 23+2 应该是 23 2 + 1.操作数可能是浮点数 比如 2.3+2 应该是 2.3 2 + 2.可能是负数 比如 -2+3 应该是 -2 3 + 比如 3+(-2) 应该是 3 -2 + 3.正数可能带有正号 比如 +3+2 应该是 3 2 + 比如 3+(+2) 应该是 3 2 +
然后处理下空格就可以了
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a) memset(a, 0, sizeof(a)) using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = 3.14159265358979323846264338327; const double E = exp(1); const double eps = 1e-6; const int INF = 0x3f3f3f3f; const int maxn = 1e3 + 5; const int MOD = 1e9 + 7; bool isdigit(char c) { if ((c >= '0' && c <= '9') || c == '.') return true; return false; } int main() { string s; cin >> s; int len = s.size(); stack <char> q; string ans = ""; map <char, int> m; m['+'] = 1; m['-'] = 1; m['*'] = 2; m['/'] = 2; int flag = 0; for (int i = 0; i < len; i++) { if (flag) flag = 0; else if (i && !isdigit(s[i - 1]) && isdigit(s[i]) && ans.size()) ans += " "; if (isdigit(s[i])) ans += s[i]; else { if (s[i] == '*' || s[i] == '/') { if (q.empty()) q.push(s[i]); else if (m[s[i]] > m[q.top()]) q.push(s[i]); else if (m[s[i]] <= m[q.top()]) { while (m[q.top()] >= m[s[i]]) { if (ans.size()) ans += " "; ans += q.top(); q.pop(); if (q.empty()) break; } q.push(s[i]); } } else if (s[i] == '+') { if (i == 0 || s[i - 1] == '(') continue; else if (q.empty()) q.push(s[i]); else { while (m[q.top()] >= m[s[i]]) { if (ans.size()) ans += " "; ans += q.top(); q.pop(); if (q.empty()) break; } q.push(s[i]); } } else if (s[i] == '-') { if (i == 0 || s[i - 1] == '(') { ans += "-"; flag = 1; } else if (q.empty()) q.push(s[i]); else { while (m[q.top()] >= m[s[i]]) { if (ans.size()) ans += " "; ans += q.top(); q.pop(); if (q.empty()) break; } q.push(s[i]); } } else if (s[i] == '(') q.push(s[i]); else if (s[i] == ')') { while (q.top() != '(') { if (ans.size()) ans += " "; ans += q.top(); q.pop(); } q.pop(); } } } while (!q.empty()) { ans += " "; ans += q.top(); q.pop(); } cout << ans << endl; }转载于:https://www.cnblogs.com/Dup4/p/9433220.html
