LQ0221 逆波兰表达式【程序填空】

题目来源：蓝桥杯2013初赛 C++ A组F题

题目描述
本题为代码补全填空题，请将题目中给出的源代码补全，并复制到右侧代码框中，选择对应的编译语言（C/Java）后进行提交。若题目中给出的源代码语言不唯一，则只需选择其一进行补全提交即可。复制后需将源代码中填空部分的下划线删掉，填上你的答案。提交后若未能通过，除考虑填空部分出错外，还需注意是否因在复制后有改动非填空部分产生错误。

正常的表达式称为中缀表达式，运算符在中间，主要是给人阅读的，机器求解并不方便。

例如：3 + 5 * (2 + 6) - 1

而且，常常需要用括号来改变运算次序。

相反，如果使用逆波兰表达式（前缀表达式）表示，上面的算式则表示为：

• • 3 * 5 + 2 6 1

不再需要括号，机器可以用递归的方法很方便地求解。

为了简便，我们假设：

1. 只有 + - * 三种运算符
2. 每个运算数都是一个小于10的非负整数下面的程序对一个逆波兰表示串进行求值。 其返回值为一个结构：其中第一元素表示求值结果，第二个元素表示它已解析的字符数。

请分析代码逻辑，并推测划线处的代码。

源代码
C

#include 

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

int main()
{
    printf("%d\n",evaluate("-+3*5+261").result);
    printf("%d\n",evaluate("+*35*42").result);
    return 0;
}
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

Java

import java.util.*;
public class Main
{
    static int[] evaluate(String x)
    {
        if(x.length()==0) return new int[] {0,0};
        
        char c = x.charAt(0);
        if(c>='0' && c<='9') return new int[] {c-'0',1};
        
        int[] v1 = evaluate(x.substring(1));
        int[] v2 =  ____________;
        
        int v = Integer.MAX_VALUE;
        if(c=='+') v = v1[0] + v2[0];
        if(c=='*') v = v1[0] * v2[0];
        if(c=='-') v = v1[0] - v2[0];
        
        return new int[] {v,1+v1[1]+v2[1]};
    }
    
    public static void main(String[] args)
    {
        System.out.println(evaluate("-+3*5+261")[0]);
        System.out.println(evaluate("+*35*42")[0]);
    }
}
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

问题分析
C语言程序填入“evaluate(x+v1.n+1)”
Java语言程序填入“evaluate(x.substring(1+v1[1]))”

AC的C语言程序如下：

#include 

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+v1.n+1);
    
    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()
{
    printf("%d\n",evaluate("-+3*5+261").result);
    printf("%d\n",evaluate("+*35*42").result);
    return 0;
}
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

AC的Java语言程序如下：

import java.util.*;
public class Main
{
    static int[] evaluate(String x)
    {
        if(x.length()==0) return new int[] {0,0};
        
        char c = x.charAt(0);
        if(c>='0' && c<='9') return new int[] {c-'0',1};
        
        int[] v1 = evaluate(x.substring(1));
        int[] v2 =  evaluate(x.substring(1+v1[1]));
        
        int v = Integer.MAX_VALUE;
        if(c=='+') v = v1[0] + v2[0];
        if(c=='*') v = v1[0] * v2[0];
        if(c=='-') v = v1[0] - v2[0];
        
        return new int[] {v,1+v1[1]+v2[1]};
    }
    
    public static void main(String[] args)
    {
        System.out.println(evaluate("-+3*5+261")[0]);
        System.out.println(evaluate("+*35*42")[0]);
    }
}
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