package club.wujingjian;

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

public class Test {
    /**
     * 中缀表达式
     * 2 + 3
     * 3 + 4 + 5
     * 后缀表达式(逆波兰表达式)
     * 1 2 +
     * 3 4 5 + +
     * 计算机计算的时候,先把中缀表达式 转换为后缀表达式,然后再进行计算
     * ["4","13","5","/","+"]     (4 + (13 / 5))
     * ["4","2","+"]
     * ["6"]
     * <p>
     * 思路:
     * a.如果元素不是 + - * /中的某一个,就入栈
     * b.如果元素是+ - * /中的某一个,则从栈中连续弹出两个元素,并对这两个元素进行计算,将结果入栈
     * 最后栈中只有一个数,这个数就是结果
     */

    public static int calc_exp(String arr) {
        List<String> fuhao = new ArrayList<String>();
        fuhao.add("+");
        fuhao.add("-");
        fuhao.add("*");
        fuhao.add("/");
        String exp[] = arr.split(",");
        Stack.StackData stackData = new Stack.StackData(exp.length);
        for (int i = 0; i < exp.length; i++) {
            String tmp = exp[i];
            if (!fuhao.contains(tmp)) {
                stackData.push(tmp);
            } else {
                int a = Integer.parseInt(stackData.pop());
                int b = Integer.parseInt(stackData.pop());
                if (tmp.equals("+")) {
                    stackData.push((b+a)+"");
                } else if (tmp.equals("-")) {
                    stackData.push((b -a )+"");
                }else if (tmp.equals("*")) {
                    stackData.push((b *a )+"");
                }else if (tmp.equals("/")) {
                    stackData.push((b / a )+"");
                }
            }
        }
        return Integer.parseInt(stackData.getTopElement());
    }

    public static void main(String[] args) {
        //"4","13","5","/","+"
        String str = "4,13,5,/,+";
        System.out.println(str + "  的计算结果是:" +calc_exp(str));
    }

}

package club.wujingjian;

import java.util.Scanner;

public class Stack {

    /**
     * 栈结构
     * 输入一堆括号,看是否括号符合匹配
     * (a(b)c) 匹配
     * (((fd))()) 匹配
     * (a(b)c)) 不合法
     * 思路:
     * 栈是先进后出的
     * 如果遇到左括号   进栈处理
     * 如果遇到又括号   判断栈是否为空,不为空则出栈一下;如果为空,说明当前右括号无匹配的左括号(判定为不合法)
     * 所有输入都遍历完了,判断栈是否为空,如果为空则说明合法匹配,否则说明括号非成对出现.
     * @param args
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String inputStr = scanner.nextLine();
        StackData data = new StackData(inputStr.length());
        for (int i = 0; i < inputStr.length(); i++) {
            String tmp = inputStr.charAt(i)+"";
            if (tmp.equals("(")) {
                data.push(tmp);
            } else if (tmp.equals(")")) {
                if (!data.isEmpty()) {
                    data.pop();
                } else {
                    System.out.println("不合法的括号匹配");
                    return;
                }
            }
        }
        if (data.isEmpty()) {
            System.out.println("合法");
        } else {
            System.out.println("不合法");
        }
    }

    static class StackData {
        private String[] items;
        private int count = 0;

        public StackData(int length){
            items = new String[length];
        }

        public void push(String item) {
            items[count] = item;
            count++;
        }

        public String pop (){
            return items[--count];
        }

        public boolean isEmpty(){
            return count ==0;
        }

        public String getTopElement(){
            int t = count;
            return items[t-1];
        }

    }
}

扩展1: 要求实现一个可以返回栈内最小元素的方法。

可以定义两个栈，压栈时候同时往两个里面放，一个栈存放数据，另一个栈存放最小元素，当最小元素栈为空，则直接入栈，否则，比较入栈元素< 最小元素栈顶元素 则入栈 将要入栈的元素，否则入栈最小元素栈顶元素。

扩展2

java实现中缀表达式转后缀表达式,并且计算结果。

Calculator.java

package algorithm;

import java.util.*;
import java.util.regex.Pattern;

public class Calculator {

    private static Map<Character,Integer> operator = new HashMap<>();

    static {
        operator.put('+',1);
        operator.put('-',1);
        operator.put('*',2);
        operator.put('/',2);
    }

    /**
     * 将中缀表达式转换为后缀表达式
     * 遍历中缀表达式的每一可用项
     * 1.如果是数字则放入后缀表达式列表中
     * 2.如果是左括号则放入栈中
     * 3.如果是运算符(+*-/) 则取栈顶元素判断运算符优先级,
     *  a. 如果栈顶元素优先级大于等于当前项,则将栈顶元素出栈并存入 后缀表达式中,
     *  b. 否则将当前项入栈
     * 4.如果是右括号,则取出栈顶元素判断是否是左括号,如果不是左括号,则将栈顶元素放入后缀表达式中,然后继续取栈顶元素,直到碰到左括号终止
     * @param s
     * @return
     */
    public Object[] compile(String s) {
        //首先将中缀表达式的每一个可用项(排除空格)都转换为数组中的每一项,数字存入Integer,运算符存入字符串
        Object[] parsed = parseAsExpression(s);
        List<Object> output = new LinkedList<>();
        Deque<Character> stack = new LinkedList<>();
        for (Object e : parsed) {
            if (e instanceof Integer) {
                output.add((Integer) e);
            } else {
                char ch = (Character) e.toString().charAt(0);//这里运算符只能为(+-*/)所以取第一个字符就行,方便接下来switch判断
                switch (ch) {
                    case ')':
                        // find '(' in stack
                        for (; ; ) {
                            if (stack.isEmpty()) {
                                throw new IllegalStateException("Compile error");
                            }
                            char top = stack.pop();
                            if (top == '(') {
                                break;
                            } else {
                                output.add(top);
                            }
                        }
                        break;
                    case '(':
                        stack.push(ch);
                        break;
                    case '+':
                    case '-':
                    case '*':
                    case '/':
                        //find all operators that >= ch
                        while (!stack.isEmpty()) {
                            int count =0;
                            char first = stack.peek();
                            if(operator.containsKey(first) && operator.get(first) >= operator.get(ch)) {
                                count ++;
                                stack.pop();
                                output.add(first);
                            }else {
                                break;
                            }
                        }
                        stack.push(ch);
                        break;
                    default:
                        throw new IllegalStateException("Compile error: " + s + " for " + ch);
                }
            }
        }
        while (!stack.isEmpty()) {
            output.add(stack.pop());
        }
        return output.toArray();
    }

    //计算后缀表达式
    public int calculate(Object[] expression) {
        Deque<Integer> stack = new LinkedList<>();
        for (Object e : expression) {
            if (e instanceof Integer) {
                stack.push((Integer) e);
            } else {
                char op = (Character) e;
                int n1 = stack.pop();
                int n2 = stack.pop();
                int r = operate(op, n2, n1);
                stack.push(r);
            }
        }
        return stack.pop();
    }

    /**
     * 将中缀表达式中每一项都转为数组中的一项,其中如果是数字则放入Integer对象.否则肯定为+,-,*,/中的一项
     * @param s
     * @return
     */
    Object[] parseAsExpression(String s) {
        String [] arr = s.replaceAll("\\+"," + ")
                .replaceAll("\\-"," - ")
                .replaceAll("\\*"," * ")
                .replaceAll("\\/"," / ")
                .replaceAll("\\("," ( ")
                .replaceAll("\\)"," ) ").split(" ");
        List<Object> result = new ArrayList<>();
        List<Object> resultWrap = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            if (!"".equals(arr[i])) {
                result.add(arr[i]);
            }
        }
        for (int i = 0; i < result.size(); i++) {
            if (isInteger(result.get(i).toString())) {
                resultWrap.add(Integer.parseInt(result.get(i).toString()));
            }else {
                resultWrap.add(result.get(i));
            }

        }
        return resultWrap.toArray();
    }

    public int operate(char op, int first, int second) {
        switch (op) {
            case '+':
                return first + second;
            case '-':
                return  first - second;
            case '*':
                return first * second;
            case '/':
                return first/second;
            default:
                throw new IllegalArgumentException("参数错误");
        }
    }


    public static boolean isInteger(String str) {
        Pattern pattern = Pattern.compile("[0-9]*");
        return pattern.matcher(str).matches();
    }
}

测试类Main

package algorithm;

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

public class Main {

    /**
     * 中缀表达式  "1 + 2 * (9 - 5)"
     * 对应后缀表达式 1 2 9 5 - * +
     * @param args
     */
    public static void main(String[] args) {
        test("1 + 2 * (9 - 5)");
        test("1 / 2 + (9 - 5)");
        test("1 * 2 + (9 - 5)");
        test("1 * 2 * 3 * 5 + (9 - 5)");
        test("1 * 2 * 3 * 5 + 18 + 5 + 4 / 3 + (9 - 5)");
        test("10*2*3*5+ 18 + 5 + 4 / 3 + (9 - 5)");
        test("10*2*3*5+ 18 + (5 + 4) / 3 + (9 - 5)");
    }

    static void test(String s){
        Calculator calc = new Calculator();
        Object[] exp = calc.compile(s);
        int result = calc.calculate(exp);
        System.out.println("[calculate] " + s + " => " + expressionToString(exp) + " ==> " + result);
    }

    static String expressionToString(Object[] exp) {
        List<String> list = new ArrayList<>(exp.length);
        for(Object e: exp) {
            list.add(e.toString());
        }
        return list.toString();
    }
}