Java实现一个简单的计算器

发表于 更新于 分类于 阅读次数： 本文字数： 2.6k 阅读时长 ≈ 2 分钟

Java实现一个简单的计算器

在LeetCode上有几道题目实现简单的计算器，最近刚刚在Algorithms (4th edition)上学习了利用栈实现简单的计算器，使用的是 E.W.Dijkstra在1960s提出的栈算法实现的。利用栈后进先出的特性，可以实现对括号以及优先级的处理。第一次尝试这种算法，写出来的代码效率也不是很高。

基本想法

首先，初始化两个栈，一个用来存储运算符（包括括号和各种运算符)。Stack<String> ops = new Stack<String>(); Stack<Integer> vals = new Stack<Integer>();第一个程序实现的是只包括加减的，因此没有运算优先顺序，只需要考虑括号，空格等字符。基本想法是：向standard input内输入一个字符串表达式，然后对数字和符号进行各自对应的处理。遇到一个数字，push进vals栈，遇到一个运算符，先判断在ops中的上一个字符是否可以进行运算（之所以这样子做是因为这样子也可以方便判断优先级），若可以进行运算，那么就将ops中的一个符号和vals的数pop出来进行对应的运算，然后将当前的运算符push进ops，否则，直接将当前符号push进ops。如果遇到右括号，直接对栈中的元素进行运算直到遇到左括号。

对于字符串转整型的处理

首先，我们可以设置一个int flag = 0，若读取的当前字符为数字，那么就将flag的值设为1，并且将这个数字转化为int入栈。若当前的字符不为数字，记得一定要将flag的值重新设为0。代码

1
2
3
4
5
6
7
8
9
10
11
int flag = 0;
for(int i = 0; i < length; i++){
    String currentString = s.subString(i,i+1);
    if(currentChar.charAt(0) >= '0' && currentChar.charAt(0) <= '9'){
        if(flag == 0)
            vals.push(Integer.parseInt(currentChar));
        else
       	vals.push(Integer.parseInt(Integer.toString(vals.pop())+currentChar()));
        flag = 1;
    }
}

完整代码

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
class Solution {
    public static int calculate(String s) {
        int length = s.length();
        Stack<String> ops = new Stack<String>();
        Stack<Integer> vals = new Stack<Integer>();
        int flag = 0;
        for (int i = 0; i < length; i++) {
            String currentChar = s.substring(i, i + 1);
            //将当前位置的字符转化为字符串
            if (currentChar.equals(" "))
                continue;
            if (currentChar.charAt(0) >= '0' && currentChar.charAt(0) <= '9') {
                if (flag == 0)
                    vals.push(Integer.parseInt(currentChar));
                else
                    vals.push(Integer.parseInt(Integer.toString(vals.pop()) + currentChar));
                flag = 1;
                continue;
            }
            else if (currentChar.equals("(");
                ops.push(currentChar);
            else if (currentChar.equals("+") || currentChar.equals("-")){
                if(ops.isEmpty());
                else if(ops.peek().equals("+") || ops.peek().equals("-")){
                    int x = vals.pop();
                    String op = ops.pop();
                    if(op.equals("+"))
                        x = vals.pop() + x;
                    else if(op.equals("-"))
                        x = vals.pop() - x;
                    vals.push(x);
                }
                ops.push(currentChar);
            }
            else if (currentChar.equals(")")) {
                String op = ops.pop();
                while (!op.equals("(")) {
                    int x = vals.pop();
                    if (op.equals("+"))
                        x = vals.pop() + x;
                    else if (op.equals("-"))
                        x = vals.pop() - x;
                    vals.push(x);
                    if (!ops.isEmpty())
                        op = ops.pop();
                }
            }
            flag = 0;
        }
        while (!ops.isEmpty()) {
            String op = ops.pop();
            int x = vals.pop();
            if (op.equals("+"))
                x = vals.pop() + x;
            else if (op.equals("-"))
                x = vals.pop() - x;
            vals.push(x);
        }
        return vals.pop();
    }
}