Jobdu-27-简单计算器

Posted on | In

Stack

Question

表达式求值

Answer

  1. 设立两个堆栈，一个用来保存运算符，另一个用来保存数字
  2. 在表达式首尾添加标记运算符，该运算符运算优先级最低
  3. 从左至右依次遍历字符串，若遍历到运算符，则将其运算符栈栈顶元素进行比较，若运算符栈栈顶运算符优先级小于该运算符或者此时运算符栈为空，则将该运算符压入堆栈。遍历字符串中下一个元素。
  4. 若运算符栈栈顶运算符优先级大于该运算符，则弹出该栈顶元素，再从数字栈中依次弹出两个栈顶数字，完成弹出的运算符对应的运算得到的结果后，再将该数字压入数字栈中，重复比较此时栈顶运算符与当前遍历到的运算符优先级，使其优先级大小重复步骤3或步骤4
  5. 若遍历到表达式中的数字，则直接压入数字栈
  6. 若运算符堆栈中仅存有两个运算符且栈顶元素为我们人为添加的标记运算符，那么表达式结束，此时数字堆栈中唯一的数字即为表达式的值
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
81
82
83
84
85
86
87
88
import java.util.Scanner;
import java.util.Stack;
public class MyClass{
    public boolean retop; // operator
    public int retnum; // number
    public int i;
    
    public static int[][] arr = {{1,0,0,0,0}, {1,0,0,0,0}, {1,0,0,0,0}, {1,1,1,0,0}, {1,1,1,0,0}};
    
    public static int getOp(MyClass obj, Stack<Integer> operator, String[] s){
        if(obj.i == 0 && operator.isEmpty()){
            obj.retop =  true;
            obj.retnum = 0;
            return 0;
        } // ???
        if(obj.i >= s.length){
            obj.retop = true;
            obj.retnum = 0;
            return 0;
        } // ???
        if(s[obj.i].matches("[0-9]*")){
            obj.retop = false;
            obj.retnum =  Integer.parseInt(s[obj.i]);
        }else{
            obj.retop = true;
            if(s[obj.i].equals("+"))
                obj.retnum = 1;
            else if(s[obj.i].equals("-"))
                obj.retnum = 2;
            else if(s[obj.i].equals("*"))
                obj.retnum = 3;
            else if(s[obj.i].equals("/"))
                obj.retnum = 4;
        }
        obj.i++;
        return 0;
    }
    
    public static void main(String[] args){
    	System.out.println("hello world");
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            Stack<Integer> operator = new Stack<>();
            Stack<Double> number = new Stack<>();
            String str = sc.nextLine();
            if(str.charAt(0) == '0')
                break;
            String[] s = str.split(" ");
//            for(String ss:s)
//            	System.out.println(ss);
            MyClass obj = new MyClass();
            while(true){
            	getOp(obj, operator, s);
            	if(obj.retop == false)
            		number.push((double) obj.retnum);
            	else{
            		double temp = 0.0;
            		if(operator.isEmpty() || arr[obj.retnum][operator.peek()] == 1)
            			operator.push(obj.retnum);
            		else{
            			//当前运算符小于栈顶运算符，一直出栈
            			while(arr[obj.retnum][operator.peek()] == 0){
            				int temp_op = operator.pop();
            				double b = number.pop();
            				double a = number.pop();
            				if(temp_op == 1)
            					temp = a + b;
            				else if(temp_op == 2)
            					temp = a - b;
            				else if(temp_op == 3)
            					temp = a * b;
            				else if(temp_op == 4)
            					temp = a / b;
            				number.push(temp);
            			}
            		}
            		
            	}
            	if(operator.size() == 2 && operator.peek() == 0)
        			break;
            }
            System.out.printf("%.2f%n", number.peek());
        }
        
    }
}