2、数组模拟栈&栈的表达式求值

AcWing 828. 模拟栈

AcWing 3302. 表达式求值

import java.util.*;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.zhan();
    }

    int N=100010;
    int a[]=new int[N];
    int top=-1;
    //数组模拟栈
    void push(int x) {
        a[++top]=x;
    }
    int pop() {
        return a[top--];
    }

    String empty() {
        if(top==-1){
            return "YES";
        }else{
            return "NO";
        }
    }

    int query() {
        return a[top];
    }

    void zhan() {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        for (int i = 0; i < n; i++) {
            String d=scanner.next();
            if(d.equals("push")){
                int k=scanner.nextInt();
                push(k);
            }if(d.equals("query")){
                System.out.println(query());
            }if(d.equals("pop")){
                pop();
            }if(d.equals("empty")){
                System.out.println(empty());
            }
        }
    }
}

栈的表达式求值

import java.util.*;

//栈的表达式求值
//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.zifuchuanyunsuan();

    }

    Stack<Integer> num = new Stack();
    Stack<Character> op = new Stack();
    HashMap<Character, Integer> preop = new HashMap();

    void eval() {
        int b = num.pop();
        int a = num.pop();
        char c = op.pop();
        int x = 0;
        if (c == '+') x = a + b;
        if (c == '-') x = a - b;
        if (c == '*') x = a * b;
        if (c == '/') x = a / b;
        num.push(x);
    }

    void zifuchuanyunsuan() {
        preop.put('+', 1);
        preop.put('-', 1);
        preop.put('*', 2);
        preop.put('/', 2);
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        char[] ss = s.toCharArray();
        for (int i = 0; i < ss.length; i++) {
            char item = ss[i];
            if (item >= '0' && item <= '9') {
                int j = i, x = 0;
                while (j < ss.length && ss[j] >= '0' && ss[j] <= '9')
                    x = x * 10 + ss[j++] - '0';
                i = j - 1;
                num.push(x);
            } else if (item == '(') {
                op.push(item);
            } else if (item == ')') {
                while (op.peek() != '(') eval();
                op.pop();
            } else {
                //item是运算符，例如+-*/
                while (op.size() != 0 && op.peek() != '(' && preop.get(op.peek()) >= preop.get(item)) eval();
                op.push(item);
            }
        }

        while (op.size() != 0) eval();

        System.out.println(num.pop());
    }
}