算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。前缀表达式指二元运算符位于两个运算数之前,例如2+3*(7-4)+8/4
的前缀表达式是:+ + 2 * 3 - 7 4 / 8 4
。请设计程序计算前缀表达式的结果值。
输入格式:
输入在一行内给出不超过30个字符的前缀表达式,只包含+
、-
、*
、/
以及运算数,不同对象(运算数、运算符号)之间以空格分隔。
输出格式:
输出前缀表达式的运算结果,保留小数点后1位,或错误信息ERROR
。
输入样例:
输出样例:
思路
求前缀表达式的值,需要从右向左读,遇数字压栈,遇符号使用两次栈顶元素进行计算,并将结果压栈。最后若栈内元素唯一,则为最终结果。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
| #include <iostream> #include <stdlib.h> #include <cstdio> #include <cstring> #include <stack> #include <string> using namespace std; int main() { stack<double> b; string s[1000]; int n = 0; while (cin >> s[n++]) { } int f = 1; n--; for (int i = n - 1; i >= 0; i--) { if (s[i].length() == 1 && (s[i][0] == '+' || s[i][0] == '-' || s[i][0] == '*' || s[i][0] == '/')) { double x, y; if (b.size() < 2) { f = 0; break; } x = b.top(); b.pop(); y = b.top(); b.pop(); if (s[i][0] == '+') { b.push(x + y); } else if (s[i][0] == '-') { b.push(x - y); } else if (s[i][0] == '*') { b.push(x * y); } else if (s[i][0] == '/') { if (y == 0) { f = 0; break; } b.push(x / y); } } else { double x = atof(s[i].c_str()); b.push(x); } } if (b.size() != 1) f = 0; if (f) printf("%.1lf", b.top()); else cout << "ERROR"; return 0; }
|