脚踏实地

class TwoDimensionArrayDemo {
  // 将二维数组转换为稀疏数组
  public static int[][] twoDimensionArrayToSparseArray(int[][] array) {
    // 记录棋盘中有效值的数量
    int sum = 0;
    int row = array.length;
    int column = 0;
    for (int[] ints : array) {
      column = ints.length;
      for (int item : ints) {
        if (item != 0) {
          sum++;
        }
      }
    }

    // 创建稀疏数组
    int[][] sparseArray = new int[sum + 1][3];
    sparseArray[0][0] = row;
    sparseArray[0][1] = column;
    sparseArray[0][2] = sum;

    // 给稀疏数组赋值
    int count = 0;
    for (int i = 0; i < array.length; i++) {
      for (int j = 0; j < array[i].length; j++) {
        if (array[i][j] != 0) {
          count++;
          sparseArray[count][0] = i;
          sparseArray[count][1] = j;
          sparseArray[count][2] = array[i][j];
        }
      }
    }

    System.out.println("稀疏数组====》");
    for (int i = 0; i < sparseArray.length; i++) {
      System.out.printf("%d\t%d\t%d\t\n", sparseArray[i][0], sparseArray[i][1], sparseArray[i][2]);
    }
    return sparseArray;
  }
}

class TwoDimensionArrayDemo {
  // 稀疏数组转二维数组
  public static int[][] sparseArrayToTwoDimensionArray(int[][] sparseArray) {
    int[][] toTwoDimensionArray = new int[sparseArray[0][0]][sparseArray[0][1]];
    // 给二维数组赋值
    for (int i = 1; i < sparseArray.length; i++) {
      toTwoDimensionArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
    }

    System.out.println("二维数组====》");
    for (int[] row : toTwoDimensionArray) {
      for (int data : row) {
        System.out.printf("%d\t", data);
      }
      System.out.println();
    }
    return toTwoDimensionArray;
  }
}

class SingleLinkedList{

    // 头结点
    private Node headNode = new Node(0,"");

    // 添加方法
    public  void add(Node node){
        Node tmpNode = headNode;

        while (tmpNode.next != null){
            // 指向下一个结点
            tmpNode = tmpNode.next;
        }
        // 退出循环意味着tmpNode.next == null 即找到最后一个结点了
        tmpNode.next = node;
    }

    // 顺序添加
    public void addByOrder(Node node){
        boolean flag = false;
        Node tmp = headNode;
        while (true){
            if (tmp.next == null) {
                break;
            }

            // 将新插入的结点num跟链表中已经存在的num进行比较，如果 < 链表中的结点 则说明找到了该位置
            if (node.num < tmp.next.num){
                break;
            }
            // 如果num相同则不能添加
            if (node.num == tmp.next.num){
                flag = true;
                break;
            }
            tmp = tmp.next;
        }

        if (!flag){
            node.next = tmp.next;
            tmp.next = node;
            return;
        }
        System.out.printf("需要添加的结点编号：%d已经存在了",node.num);
    }

    // 遍历链表
    public void list() {
        // 遍历除了头结点外的所有结点
        Node tmpNode = headNode.next;
        if (tmpNode == null){
            System.out.println("链表为空！");
            return;
        }

        while (tmpNode != null){
            System.out.println(tmpNode);
            // 指向下一个结点
            tmpNode = tmpNode.next;
        }
    }


}


class Node {

    int num;
    String name;
    Node next;

    public Node(int num,String name){
        this.num = num;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "num=" + num +
                ", name='" + name + '\'' +
                '}';
    }
}

class LinkedListDemo{
    // 反转链表
    public void reserve(Node head) {
      if (head.next == null || head.next.next == null) {
        return;
      }

      Node reserve = new Node(0, "");
      Node cur = head.next;
      Node next = null;
      // 遍历链表
      // 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
      while (cur != null) {

        // 保存当前结点的下一个结点
        next = cur.next;

        // 将cur的下一个节点指向新的链表的最前端（覆盖掉）保证将最新的结点放到reseve的最前面
        cur.next = reserve.next;

        // 将cur 连接到新的链表上
        reserve.next = cur;

        // 将之前保存好的结点赋值给当前结点
        cur = next;
      }
    }
}

class LinkedListDemo {
  public void reservePrint(Node head) {
    if (head.next == null || head.next.next == null) {
      return;
    }

    Stack<Node> nodes = new Stack<>();
    Node tmp = head.next;
    while (tmp != null) {
      nodes.push(tmp);
      tmp = tmp.next;
    }

    // 从stack中取出结点
    while (nodes.size() > 0) {
      System.out.println(nodes.pop());
    }
  }
}

class DoubleLinkedList{

    // 头结点
    private Node headNode = new Node(0,"");


    public Node getHeadNode() {
        return headNode;
    }


    // 添加方法
    public  void add(Node node){
        Node tmpNode = headNode;

        while (tmpNode.next != null){
            // 指向下一个结点
            tmpNode = tmpNode.next;
        }
        // 退出循环意味着tmpNode.next == null 即找到最后一个结点了
        tmpNode.next = node;
        node.prev = tmpNode;
    }


    // 双向链表修改
    public void update(Node node){
        if (headNode == null) {
            return;
        }

        Node tmp = headNode.next;
        while (true){
            if (tmp == null){
                break;
            }
            if (node.num == tmp.num){
                tmp.name = node.name;
                break;
            }
            tmp = tmp.next;
        }
    }

    // 双向链表删除
    public void remove(int num){
        if (headNode.next == null){
            System.out.println("链表为空，无法删除！");
            return;
        }
        Node tmp = headNode.next;
        while (tmp != null){
            if (num == tmp.num){
                tmp.prev.next = tmp.next;

                // 最后一个结点的next 为null null.pre会出现空指针异常
                if(tmp.next != null) {
                    tmp.next.prev = tmp.prev;
                }
                break;
            }
            tmp = tmp.next;
        }
    }

    // 遍历链表
    public void list() {
        // 遍历除了头结点外的所有结点
        Node tmpNode = headNode.next;
        if (tmpNode == null){
            System.out.println("链表为空！");
            return;
        }

        while (tmpNode != null){
            System.out.println(tmpNode);
            // 指向下一个结点
            tmpNode = tmpNode.next;
        }
    }


}


class Node {

    int num;
    String name;
    Node next;
    Node prev;

    public Node(int num,String name){
        this.num = num;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "num=" + num +
                ", name='" + name + '\'' +
                '}';
    }
}

class JoesphSingletonLinkedList {

    private Node first = null;

    // 向单向链表添加数据
    public void add(int nums) {
        if (nums < 1) {
            System.out.println("nums的值不正确");
            return;
        }
        Node cur = null;
        for (int i = 1; i <= nums; i++) {
            Node node = new Node(i);
            if (i == 1) {
                first = node;
                first.next = first;
                cur = first;
            } else {
                cur.next = node;
                node.next = first;
                cur = node;
            }
        }
    }

    // 遍历单向循环链表
    public void list() {
        Node tmp = first;
        while (true){
            System.out.printf("当前结点为：%d\n",tmp.num);
            if (tmp.next == first){
                break;
            }
            tmp = tmp.next;
        }
    }

    // 约瑟夫问题
    public void joseph(int startNum,int countNum,int sum){
        if (startNum > sum || startNum < 0 || countNum < 0) {
            System.out.println("输入的参数不正确！");
            return;
        }
        // 创建辅助指针，将该指针指向 first 的前一个
        Node helper = first;
        while (helper.next != first) {
            helper = helper.next;
        }

        // 将first 和 help指针循环 （startNum - 1）次；因为从startNum开始，需要减一
        for (int i = 0; i < startNum - 1; i++) {
            first = first.next;
            helper = helper.next;
        }

        while (true){
            // 当环形链表中只存在一个结点
            if (first == helper){
                break;
            }

            // 因为是环形链表，所以需要循环挨个出链表
            for (int i = 0; i < countNum - 1; i++) {
                first = first.next;
                helper = helper.next;
            }

            // 当前 first 就是出圈的结点
            System.out.printf("当前出队列的结点编号为：%d\n",first.num);
            first = first.next;
            helper.next = first;
        }
        System.out.printf("最后的结点为：%d\n",first.num);
    }

}

class Node {

    int num;
    Node next;

    public Node(int num){
        this.num = num;
    }

    @Override
    public String toString() {
        return "Node{" +
                "num=" + num +
                '}';
    }
}

class ArrayStack<T>{

    private int size;
    private int top;
    private Object[] stack;

    public ArrayStack(int size) {
        this.size = size;
        this.stack = new String[size];
        top = -1;
    }

    public boolean isFull(){
        return top == size -1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    // 入栈
    public void push(T item) {
        if (isFull()) {
            System.out.println("栈已经满了，不能继续添加！");
            return;
        }
        top++;
        this.stack[top] = item;
    }

    // 出栈操作
    public T pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈已经为空，不能继续pop");
        }
        T val = (T)this.stack[top];
        top--;
        return val;
    }

    // 遍历栈
    public void list() {
        if (isEmpty()) {
            System.out.println("栈为空不能继续遍历！");
            return;
        }

        System.out.println("遍历栈==》");
        for (int i = top; i >=0; i--){
            System.out.println(this.stack[i]);
        }
    }

}

class CalcInfixExpressions {


    public int calcInfixExpressions(String expression) {
        // 定义变量
        char[] chars = expression.toCharArray();
        int len = chars.length;
        Stack<Integer> numStack = new Stack<>();
        Stack<Character> oprStack = new Stack<>();
        int index = 0;

        for (int j = 0; j < len; j++) {

            char ch = chars[j];

            index++;

            // 判断字符是否为数字,如果是数字就放入数栈中
            if (Character.isDigit(ch)) {

                // 接收多位数
                int num = ch;
                boolean flag = false;

                // 从当前字符开始遍历，如果下一位字符不是数字，则将该数字压入栈中并退出循环，如果是数字，则需要拼接起来
                for (int i = index; i < len; i++) {
                    if (Character.isDigit(expression.charAt(i))) {
                        String strNum = String.valueOf(ch) + expression.charAt(i);
                        num = Integer.parseInt(strNum);
                        flag = true;
                        index++;
                        j++;
                    }else {
                        break;
                    }
                }
                if (!flag) {
                    num -= 48;
                }
                numStack.push(num);
                continue;
            }

            // 非数字，即运算符,如果为空直接加入栈中
            if (oprStack.isEmpty()) {
                oprStack.push(ch);
                continue;
            }

            // 如果运算符栈不为空，需要比较运算符的优先级，如果当前运算符的优先级 <= 栈顶的运算符的优先级，需要计算在压入栈中
            if (oprPriority(oprStack.peek()) >= oprPriority(ch)) {
                numStack.push(calc(numStack.pop(), numStack.pop(), oprStack.pop()));
            }

            // 将字符压入操作符栈中
            oprStack.push(ch);
        }


        // 将处理好的数据按照顺序弹出，进行计算，得到数栈中最后一个数就是最终的结果
        while (!oprStack.isEmpty()){
            numStack.push(calc(numStack.pop(), numStack.pop(), oprStack.pop()));
        }

        return numStack.pop();
    }


    // 获取字符的优先级
    private int oprPriority(int ch) {
        if (ch == '*' || ch == '/') {
            return 2;
        }
        if (ch == '+' || ch == '-') {
            return 1;
        }
        return -1;
    }


    // 计算
    private int calc(int num1, int num2, int opr) {
        int res = 0;
        switch (opr) {
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1;
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1;
                break;
        }
        return res;
    }

}

class PolandNotation{

    // 计算后缀表达式
    public int calcSuffixExceptions(String suffixExpres) {
        char[] chars = suffixExpres.toCharArray();
        Stack<Integer> stack = new Stack<>();
        int res =0;

        for (int i = 0; i < chars.length; i++) {
            char ch = suffixExpres.charAt(i);
            if (!Character.isDigit(ch)) {
                res = calc(stack.pop(),stack.pop(),ch);
                stack.push(res);
            }else {
                stack.push(ch - 48);
            }
        }
        return res;
    }

    // 计算
    private int calc(int num1, int num2, int opr) {
        int res = 0;
        switch (opr) {
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1;
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1;
                break;
            default:
                throw new RuntimeException("运算符有误");
        }
        return res;
    }

}

class InfixToPolandNotation{

    // 根据ASCII 判断是否为数字
    private boolean isNumber(char ch){
        return ch >=48 && ch <= 57;
    }

    // 获取字符的优先级
    private int oprPriority(String opr) {
        if (opr.equals("*") || opr.equals("/")) {
            return 2;
        }
        if (opr.equals("+") || opr.equals("-")) {
            return 2;
        }
        return -1;
    }

    // 将中缀表达式字符串转成中缀表达式集合
    public List<String> toInfixExceptionList(String str) {
        ArrayList<String> list = new ArrayList<>();
        int index = 0;
        StringBuilder number;
        char c;

        while (index < str.length()){
            if (!isNumber((c = str.charAt(index)))){
                list.add(String.valueOf(c));
                index++;
            }else {
                number = new StringBuilder();
                while (index < str.length() && isNumber((c = str.charAt(index)))){
                    index++;
                    number.append(c);
                }
                list.add(number.toString());
            }
        }
        return list;
    }


    // 将中缀表达式转为后缀表达式
    public List<String> infixExpressionToSuffixExpress(List<String> list) {
        Stack<String> stack = new Stack<>();
        ArrayList<String> finalList = new ArrayList<>();

        for (String item : list) {
            // 如果是数字或者为（ 将该值压入栈中
            if (item.matches("\\d+")){
                finalList.add(item);
                continue;
            }

            if (item.equals("(")){
                stack.push(item);
                continue;
            }

            // 如果是 ）则将 ()中间的数重新压入list中，最后将 ） 移除掉
            if (item.equals(")")){
                while (!stack.peek().equals("(")) {
                    finalList.add(stack.pop());
                }
                stack.pop();
            }else {
                // 如果不是 ）则判断运算符的优先级，如果符号栈栈顶的优先级 >= 当前的优先级，则将该运算符加入数字栈中
                while (stack.size() > 0 && oprPriority(stack.peek()) >= oprPriority(item)){
                    finalList.add(stack.pop());
                }
                stack.push(item);
            }
        }

        // 将operStack中剩余的运算符依次弹出并加入tempList
        while (stack.size() != 0) {
            finalList.add(stack.pop());
        }
        return finalList;
    }

}

public class ReversePolishMultiCalc {

	 /**
     * 匹配 + - * / ( ) 运算符
     */
    static final String SYMBOL = "\\+|-|\\*|/|\\(|\\)";

    static final String LEFT = "(";
    static final String RIGHT = ")";
    static final String ADD = "+";
    static final String MINUS= "-";
    static final String TIMES = "*";
    static final String DIVISION = "/";

    /**
     * 加減 + -
     */
    static final int LEVEL_01 = 1;
    /**
     * 乘除 * /
     */
    static final int LEVEL_02 = 2;

    /**
     * 括号
     */
    static final int LEVEL_HIGH = Integer.MAX_VALUE;


    static Stack<String> stack = new Stack<>();
    static List<String> data = Collections.synchronizedList(new ArrayList<String>());

    /**
     * 去除所有空白符
     * @param s
     * @return
     */
    public static String replaceAllBlank(String s ){
        // \\s+ 匹配任何空白字符，包括空格、制表符、换页符等等, 等价于[ \f\n\r\t\v]
        return s.replaceAll("\\s+","");
    }

    /**
     * 判断是不是数字 int double long float
     * @param s
     * @return
     */
    public static boolean isNumber(String s){
        Pattern pattern = Pattern.compile("^[-\\+]?[.\\d]*$");
        return pattern.matcher(s).matches();
    }

    /**
     * 判断是不是运算符
     * @param s
     * @return
     */
    public static boolean isSymbol(String s){
        return s.matches(SYMBOL);
    }

    /**
     * 匹配运算等级
     * @param s
     * @return
     */
    public static int calcLevel(String s){
        if("+".equals(s) || "-".equals(s)){
            return LEVEL_01;
        } else if("*".equals(s) || "/".equals(s)){
            return LEVEL_02;
        }
        return LEVEL_HIGH;
    }

    /**
     * 匹配
     * @param s
     */
    public static List<String> doMatch (String s) throws Exception{
        if(s == null || "".equals(s.trim())) throw new RuntimeException("data is empty");
        if(!isNumber(s.charAt(0)+"")) throw new RuntimeException("data illeagle,start not with a number");

        s = replaceAllBlank(s);

        String each;
        int start = 0;

        for (int i = 0; i < s.length(); i++) {
            if(isSymbol(s.charAt(i)+"")){
                each = s.charAt(i)+"";
                //栈为空，(操作符，或者 操作符优先级大于栈顶优先级 && 操作符优先级不是( )的优先级 及是 ) 不能直接入栈
                if(stack.isEmpty() || LEFT.equals(each)
                        || ((calcLevel(each) > calcLevel(stack.peek())) && calcLevel(each) < LEVEL_HIGH)){
                    stack.push(each);
                }else if( !stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek())){
                    //栈非空，操作符优先级小于等于栈顶优先级时出栈入列，直到栈为空，或者遇到了(，最后操作符入栈
                    while (!stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek()) ){
                        if(calcLevel(stack.peek()) == LEVEL_HIGH){
                            break;
                        }
                        data.add(stack.pop());
                    }
                    stack.push(each);
                }else if(RIGHT.equals(each)){
                    // ) 操作符，依次出栈入列直到空栈或者遇到了第一个)操作符，此时)出栈
                    while (!stack.isEmpty() && LEVEL_HIGH >= calcLevel(stack.peek())){
                        if(LEVEL_HIGH == calcLevel(stack.peek())){
                            stack.pop();
                            break;
                        }
                        data.add(stack.pop());
                    }
                }
                start = i ;    //前一个运算符的位置
            }else if( i == s.length()-1 || isSymbol(s.charAt(i+1)+"") ){
                each = start == 0 ? s.substring(start,i+1) : s.substring(start+1,i+1);
                if(isNumber(each)) {
                    data.add(each);
                    continue;
                }
                throw new RuntimeException("data not match number");
            }
        }
        //如果栈里还有元素，此时元素需要依次出栈入列，可以想象栈里剩下栈顶为/，栈底为+，应该依次出栈入列，可以直接翻转整个stack 添加到队列
        Collections.reverse(stack);
        data.addAll(new ArrayList<>(stack));

        System.out.println(data);
        return data;
    }

    /**
     * 算出结果
     * @param list
     * @return
     */
    public static Double doCalc(List<String> list){
        Double d = 0d;
        if(list == null || list.isEmpty()){
            return null;
        }
        if (list.size() == 1){
            System.out.println(list);
            d = Double.valueOf(list.get(0));
            return d;
        }
        ArrayList<String> list1 = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            list1.add(list.get(i));
            if(isSymbol(list.get(i))){
                Double d1 = doTheMath(list.get(i - 2), list.get(i - 1), list.get(i));
                list1.remove(i);
                list1.remove(i-1);
                list1.set(i-2,d1+"");
                list1.addAll(list.subList(i+1,list.size()));
                break;
            }
        }
        doCalc(list1);
        return d;
    }

    /**
     * 运算
     * @param s1
     * @param s2
     * @param symbol
     * @return
     */
    public static Double doTheMath(String s1,String s2,String symbol){
        Double result ;
        switch (symbol){
            case ADD : result = Double.valueOf(s1) + Double.valueOf(s2); break;
            case MINUS : result = Double.valueOf(s1) - Double.valueOf(s2); break;
            case TIMES : result = Double.valueOf(s1) * Double.valueOf(s2); break;
            case DIVISION : result = Double.valueOf(s1) / Double.valueOf(s2); break;
            default : result = null;
        }
        return result;

    }

    public static void main(String[] args) {
        //String math = "9+(3-1)*3+10/2";
        String math = "12.8 + (2 - 3.55)*4+10/5.0";
        try {
            doCalc(doMatch(math));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

}