-
- 44通过
- 147提交
- 题目提供者该用户不存在
- 标签云端
- 难度提高+/省选-
- 时空限制1s / 128MB
提交 讨论 题解
最新讨论更多讨论
- 这题有毒
- 抄题解棒责五十！
- 题面上的“—”是个什么鬼。…
- 关于题意的小疑问
题目描述
平常我们书写的表达式称为中缀表达式，因为它将运算符放在两个操作数中间，许多情况下为了确定运算顺序，括号是不可少的，而中缀表达式就不必用括号了。
后缀标记法：书写表达式时采用运算紧跟在两个操作数之后，从而实现了无括号处理和优先级处理，使计算机的处理规则简化为：从左到右顺序完成计算，并用结果取而代之。
例如：8–(3+2*6)/5+4可以写为：8 3 2 6*+5/–4+
其计算步骤为：8 3 2 6 * + 5 / – 4 +
8 3 12 + 5 / – 4 +
8 15 5 / – 4 +
8 3 – 4 +
5 4 + 9
编写一个程序，完成这个转换，要求输出的每一个数据间都留一个空格。
输入输出格式
输入格式：
就一行，是一个中缀表达式。输入的符号中只有这些基本符号“0123456789+-*/^()”，并且不会出现形如2*-3的格式。
表达式中的基本数字也都是一位的，不会出现形如12形式的数字。
所输入的字符串不要判错。
输出格式：
若干个后缀表达式，第I+1行比第I行少一个运算符和一个操作数，最后一行只有一个数字，表示运算结果。
输入输出样例
输入样例#1：
8–(3+2*6)/5+4
输出样例#1：
8 3 2 6 * + 5 / – 4 + 8 3 12 + 5 / – 4 + 8 15 5 / – 4 + 8 3 – 4 + 5 4 + 9
说明
运算的结果可能为负数，“/”以整除运算。并且中间每一步都不会超过2^31。
分析：中缀表达式转换为后缀表达式的一个解法：
0.定义一个栈.
1.遇到数，输出.
2.碰到左括号，直接压到栈顶.
3.碰到一个运算符，如果栈顶元素是左括号，直接压入栈顶，否则，从栈顶开始，把比这个运算符优先级大的给输出，然后压进去.
4.碰到右括号，将元素不断弹出直到遇到左括号.
那么如何进行计算呢？可以发现运算符是按照运算先后顺序出现的，我们只需要将字符串转化为数字，然后枚举到运算符直接运算及可.
#include#include #include #include #include #include #include #include using namespace std;string s,s1;int sizee,top,num[10000010];stack k;void add(char ss){ s1 += ss; s1 += ' ';}bool check(char t){ if (k.empty() || k.top() == '(') //千万不要打反了，血的教训 return true; if (k.top() == '^') return false; if (t == '^') return true; if (k.top() == '*' || k.top() == '/') return false; if (t == '*' || t == '/') return true; return false;}void jisuan(char x){ int a = num[top--], b = num[top--],t = 0; if (x == '+') t = a + b; if (x == '-') t = b - a; if (x == '*') t = a * b; if (x == '/') t = b / a; if (x == '^') t = pow(b, a); num[++top] = t;}void solve(){ for (int i = 0; i < sizee; i++) { if (s[i] >= '0' && s[i] <= '9') add(s[i]); else { if (s[i] == '(') k.push(s[i]); else { if (s[i] == ')') { while (k.top() != '(') { add(k.top()); k.pop(); } k.pop(); } else { if (!check(s[i])) { while (!check(s[i])) { add(k.top()); k.pop(); } } k.push(s[i]); } } } } while (!k.empty()) { add(k.top()); k.pop(); } cout << s1 << endl;}void print(){ for (int i = 0; i < s1.size(); i++) { if (s1[i] >= '0' && s1[i] <= '9') num[++top] = s1[i] - '0'; else { if (s1[i] == ' ') continue; jisuan(s1[i]); i++; for (int j = 1; j <= top; j++) printf("%d ", num[j]); for (int j = i + 1; j < s1.size(); j++) printf("%c", s1[j]); cout << endl; } }}int main(){ cin >> s; sizee = s.size(); solve(); print(); return 0;}