面试指南——公式字符串求值

公式字符串求值
给定一个字符串str, str表示一个公式,公式里可能有整数、加减乘除符号和左右括号,返回公式的计算结果。
可以认为给定的字符串一定是正确的公式,即不需要对str做公式有效性检查。
如果是负数,就需要用括号括起来,比如”4*(-3)”。但如果负数作为公式的开头或括号部分的开头,则可以没有括号,比如”-3*4”和”(-3*4)”都是合法的。
不用考虑计算过程中会发生溢出的情况。

/*
* 1.从左到右遍历str,开始遍历或者遇到字符时,就进行递归过程。当发现str遍历完,或者遇到字符’)’时,递归过程就结束。
* 比如”3*(4+5)+7”, 一开始遍历就进入递归过程value(str,0),在递归过程value(str,0)中继续遍历str,
* 当遇到字符'(‘时,递归过程value(str,0)又重复调用递归过程value(str,3)。
* 然后在递归过程value(str,3)中继续遍历str,当遇到字符’)’时,递归过程value(str,3)结束,
* 并向递归过程value(str,0)返回两个结果,第一结果是value(str,3)遍历过的公式字符子串的结果,即”4+5”=9,
* 第二个结果是value(str,3)遍历到的位置,即字符”)”的位置=6。\
* 递归过程valUe(Str,0)收到这两个结果后,既可知道交给value(Str,3)过程处理的字符串结果是多少(“(4+5)”的结果是9),
* 又可知道自己下一步该从什么位置继续遍历(该从位置6的下一个位置(即位置7)继续遍历)。
* 总之,value方法的第二个参数代表递归过程是从什么位置开始的,返回的结果是一个长度为2的数组,记为res.
* res[0]表示这个递归过程计算的结果,res[1]表示这个递归过程遍历到str的什么位置。
* 2.计算过程如下:
* a.先计算乘除法,剩下加减法再统一从左到右计算;
* b.遇到左括号,进入递归。遇到右括号跳出递归;
* c.注意代码中对输入字符串的数字字符的处理。
*/

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
public class 公式字符串求值 {
    public static int getValue(String str) {
        return value(str.toCharArray(), 0)[0];
    }
    //递归函数  
    public static int[] value(char[] str, int i) {
        LinkedList<String> que = new LinkedList<String>();
        int pre = 0;
        int[] bra = null;
        while (i < str.length && str[i] != ')') {
            if (str[i] >= '0' && str[i] <= '9') {
                pre = pre * 10 + str[i++] - '0';
            } else if (str[i] != '(') {
                addNum(que, pre);
                que.addLast(String.valueOf(str[i++]));
                pre = 0;
            } else {
                //递归操作
                bra = value(str, i + 1);
                pre = bra[0]; //递归过程中计算的结果
                i = bra[1] + 1; //递归过程遍历到str的什么位置
            }
        }
        addNum(que, pre);
        return new int[] { getNum(que), i };
    }
    //计算两个数的加法  
    public static void addNum(LinkedList<String> que, int num) {
        if (!que.isEmpty()) {
            int cur = 0;
            String top = que.pollLast();
            if (top.equals("+") || top.equals("-")) {
                que.addLast(top);
            } else {
                //字符串转换成整数(计算乘除)  
                cur = Integer.valueOf(que.pollLast());
                num = top.equals("*") ? (cur * num) : (cur / num);
            }
        }
        que.addLast(String.valueOf(num));
    }
    //获取加减计算的数值  
    public static int getNum(LinkedList<String> que) {
        int res = 0;
        boolean add = true;
        String cur = null;
        int num = 0;
        while (!que.isEmpty()) {
            cur = que.pollFirst();
            if (cur.equals("+")) {
                add = true;
            } else if (cur.equals("-")) {
                add = false;
            } else {
                num = Integer.valueOf(cur);
                res += add ? num : (-num);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        String exp = "48*((70-65)-43)+8*1";
        System.out.println(getValue(exp));

        exp = "4*(6+78)+53-9/2+45*8";
        System.out.println(getValue(exp));

        exp = "10-5*3";
        System.out.println(getValue(exp));

        exp = "-3*4";
        System.out.println(getValue(exp));

        exp = "3+1*4";
        System.out.println(getValue(exp));

    }

}
0 条评论
发表一条评论