题目描述
正常的表达式称为中缀表达式，运算符在中间，主要是给人阅读的，机器求解并不方便。 例如：3 5 * (2 6) - 1 而且，常常需要用括号来改变运算次序。 相反，如果使用逆波兰表达式（前缀表达式）表示，上面的算式则表示为： - 3 * 5 2 6 1 不再需要括号，机器可以用递归的方法很方便地求解。 为了简便，我们假设：
只有 - * 三种运算符 每个运算数都是一个小于10的非负整数 下面的程序对一个逆波兰表示串进行求值。 其返回值为一个结构：其中第一元素表示求值结果，第二个元素表示它已解析的字符数。
struct EV { int result; //计算结果 int n; //消耗掉的字符数 }; struct EV evaluate(char* x) { struct EV ev = {0,0}; struct EV v1; struct EV v2; if(*x==0) return ev; if(x[0]>='0' && x[0]<='9'){ ev.result = x[0]-'0'; ev.n = 1; return ev; } v1 = evaluate(x 1); v2 = _____________________________; //填空位置 if(x[0]==' ') ev.result = v1.result v2.result; if(x[0]=='*') ev.result = v1.result * v2.result; if(x[0]=='-') ev.result = v1.result - v2.result; ev.n = 1 v1.n v2.n; return ev; }
思路分析
这又是一道填空题。
逆波兰表达式，即前缀表达式，它的计算方式是这样的：每遇到一个运算符，对这个运算符之后的两个操作数进行运算。
举个栗子：
- 3 * 5 2 6 1
首先遇到 - ，那么找 - 后面的两个操作数，遇到 ，那么找 后面的两个操作数，遇到了3，所以应该是3 后面的一个操作数，但是后面又遇到了 * ，所以继续找 * 后面的两个操作数，遇到了5，所以应该是5*后面的一个操作数，但是又遇到了 ，所以继续找 后面的两个操作数，这时遇到了2和6，于是2 6变成了8（操作符 ），5*8变成了40（操作符*），3 40变成了43（操作符 ），次数操作码 - 只有一个操作数43，所以继续往后找一个操作数，遇到了1，43-1变成了结果42。
这里就是递归的思想了，就是每遇到一个操作符然后去找后面的两个操作数进行操作，用栈来描述比较适合。
AC代码
提交部分
代码语言：javascript复制x 1 v1.n测试全部代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
struct EV {
int result; //计算结果
int n; //消耗掉的字符数
};
struct EV evaluate(char *x) {
struct EV ev = {0, 0};
struct EV v1;
struct EV v2;
if (*x == 0) return ev;
if (x[0] >= '0' && x[0] <= '9') {
ev.result = x[0] - '0';
ev.n = 1;
return ev;
}
v1 = evaluate(x 1);
v2 = evaluate(x 1 v1.n); //填空位置
if (x[0] == ' ') ev.result = v1.result v2.result;
if (x[0] == '*') ev.result = v1.result * v2.result;
if (x[0] == '-') ev.result = v1.result - v2.result;
ev.n = 1 v1.n v2.n;
return ev;
}
int main() {
string test = "- 3*5 261";
cout << evaluate((char *) test.c_str()).result << ' ' << evaluate((char *) test.c_str()).n;
return 0;
}
