实现一个自己的栈(MyStack),表达式括号匹配检查及运算

• 自己的栈MyStack<E>，使用泛型参数:

import java.util.ArrayList;
import java.util.List;

public class MyStack<E> {
    private List<E> elements = new ArrayList<>();
    
    /**
     * 添加元素(入栈)
     * @param e
     */
    public void push(E e) {
        elements.add(e);
    }
    
    /**
     * 删除栈顶元素(出栈)
     * @return
     */
    public E pop() {
        return elements.remove(elements.size() - 1);
    }
    
    /**
     * 查看栈顶元素
     * @return
     */
    public E peek() {
        return elements.get(elements.size() - 1);
    }
    
    /**
     * 判断栈是否为空
     * @return
     */
    public boolean isEmpty() {
        return elements.size() == 0;
    }
}

• 表达式括号匹配检查

• 题目:检查表达式中的括号是否匹配(表达式中可能有圆括号，方括号，花括号)
• 要点:使用栈的FILO(先进后出)特性

public class Test {

    public static boolean CheckBrackets(String expr) {
        MyStack<Character> stack = new MyStack<>();
        for (int i = 0; i < expr.length(); i++) {
            char temp = expr.charAt(i);
            if (temp == '(' || temp == '[' || temp == '{') {
                stack.push(temp); //遇到左括号，入栈
            }
            else if(temp == ')' || temp == ']' || temp == '}') {
                if (!stack.isEmpty()) { //先判断栈是否为空，如果不为空，则继续进行
                    char left = stack.pop(); //遇到右括号，出栈
                    if ((temp == ')' && left != '(') || 
                            (temp == ']' && left != '[') || 
                            (temp == '}' && left != '{')) {
                        return false; //左括号与右括号不匹配
                    } 
                }
                else {
                    return false; //遇到右括号，但没有左括号与之匹配
                } 
            }
        }
        return stack.isEmpty(); //检查所有左括号是否完成匹配
    }
    
    public static void main(String[] args) {
        System.out.println(CheckBrackets("([3 + 5] * 2) + (1 * 2)"));
    }
}

• 表达式运算

• 1.需要先将表达式转为逆波兰表达式
• 2.通过转为的逆波兰表达式进行运算

package com.qfedu.day01;

class Q002 {

    // 逆波兰表达式 - 中缀表达式转逆波兰表达式
    public static double eval(String suffix) { //参数为逆波兰表达式
        MyStack<Double> stack = new MyStack<>();
        StringBuilder tempStr = new StringBuilder();
        for (int i = 0, len = suffix.length(); i < len; ++i) {
            char temp = suffix.charAt(i);
            if (temp == ' ') {
                if (tempStr.length() > 0) {
                    double num = Double.parseDouble(tempStr.toString());
                    stack.push(num);
                    tempStr.delete(0, tempStr.length());
                }
            }
            else if (temp >= '0' && temp <= '9') {
                tempStr.append(temp);
            }
            else {
                if (stack.size() >= 2) {
                    double num2 = stack.pop();
                    double num1 = stack.pop();
                    double result = 0;
                    switch (temp) {
                    case '+':
                        result = num1 + num2;
                        break;
                    case '-':
                        result = num1 - num2;
                        break;
                    case '*':
                        result = num1 * num2;
                        break;
                    case '/':
                        result = num1 / num2;
                        break;
                    }
                    stack.push(result);
                }
            }
        }
        return stack.pop();
    }

    public static String toSuffix(String expr) { //转为逆波兰表达式
        MyStack<Character> stack = new MyStack<>();
        StringBuilder suffix = new StringBuilder();
        StringBuilder tempStr = new StringBuilder();
        for (int i = 0, len = expr.length(); i < len; ++i) {
            char temp = expr.charAt(i);
            if (temp != ' ') {
                if (temp >= '0' && temp <= '9') {
                    tempStr.append(temp);
                }
                else {
                    if (tempStr.length() > 0) {
                        suffix.append(tempStr.toString() + " ");
                    }
                    tempStr.delete(0, tempStr.length());
                    if (temp == ')' || temp == ']' || temp == '}') {
                        Character op = stack.pop();
                        while (op != '(' && op != '[' && op != '{') {
                            suffix.append(op + " ");
                            if (!stack.isEmpty()) {
                                op = stack.pop();
                            }
                            else {
                                break;
                            }
                        }
                    }
                    else {
                        if (temp != '(' && temp != '[' && temp != '{') {
                            if (!stack.isEmpty()) {
                                Character op = stack.peek();
                                while (!hasLowerOrder(op, temp)) {
                                    suffix.append(stack.pop() + " ");
                                    if (!stack.isEmpty()) {
                                        op = stack.peek();
                                    }
                                    else {
                                        break;
                                    }
                                }
                            }
                        }
                        stack.push(temp);
                    }
                }
            }
        }
        if (tempStr.length() > 0) {
            suffix.append(tempStr.toString() + " ");
        }
        while (!stack.isEmpty()) {
            suffix.append(stack.pop() + " ");
        }
        return suffix.toString();
    }

    private static boolean hasLowerOrder(char op1, char op2) {
        return (op1 == '(' || op1 == '[' || op1 == '{') || ((op1 == '+' || op1 == '-') && (op2 == '*' || op2 == '/'));
    }

    // 栈(stack) - 线性结构 - FILO
    // 队列(queue) - 线性结构 - FIFO
    // 堆(heap) - 层次结构 - 完全二叉树
    public static void main(String[] args) throws Exception {
        System.out.println(eval(toSuffix("2 + 3 * 5")));
        System.out.println(eval(toSuffix("(1 + 2 + 3) * 5")));
        System.out.println(eval(toSuffix("(1 + 2) * 5 * (2 + 3)")));
        System.out.println(eval(toSuffix("(1 + 2) * (5 - 2) * 3)")));
        System.out.println(eval(toSuffix("(1 + 2) / (5 * (2 + 3))")));
        System.out.println(eval(toSuffix("{[1 + 12 + 234]} * 3456 * (45678 - 567890)")));
    }
}