蓝桥杯C/C++省赛：逆波兰表达式

题目描述

正常的表达式称为中缀表达式，运算符在中间，主要是给人阅读的，机器求解并不方便。 例如：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代码

提交部分

x+1+v1.n

测试全部代码

#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;
}