栈的应用--四则运算（中缀与后缀表达式转换）

参考链接
结合原文章，做了一定修改，增加Java源码实现

1. 概述

对于四则运算表达式的计算，是输入数据结构中栈的应用，即重点是中缀表达式转换为后缀表达式

2. 后缀表达式计算

• 为了解释后缀表达式的好处，我们先来看看，计算机是如何计算后缀表达式的
• 后缀表达式实例9 3 1 - 3 * + 10 2 / +
• 计算规则：从左到右遍历表达式的每个数字和符号，遇到数字就进栈，遇到是符号，就将处于栈顶的两个数字出栈，进行计算，然后计算结果进栈，一直到最终获得结果。

• 计算过程：

  
  image image
  image
  image

3. 中缀表达式转后缀表达式

我们把平时标准的四则运算表达式比如9+(3-1)*3+10/2叫做中缀表达式。
中缀表达式：9+(3-1)*3+10/2转换后缀表达式9 3 1 - 3 * + 10 2 / +

• 转换规则：

1. 当当前字符为数字时，直接输出；
2. 当当前字符为(时，将其压栈；
3. 当当前字符为)时，则弹出堆栈中最上的(之前的所有运算符并输出，然后删除堆栈中的(；
4. 当当前字符为运算符时，则依次弹出堆栈中优先级大于等于当前运算符的(到”(“之前为止)，输出，再将当前运算符压栈；
   最后弹出所有栈中的内容输出

• 转换过程
  image
  image
  image
  image
  image

4. 源代码实现

package data_structure;

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

/**
 * 栈的应用
 * https://blog.csdn.net/u011857433/article/details/79993385
 * 四则运算表达式求职，中缀表达式与后缀表达式转换
 */
public class ReversePoland {


    public static void main(String[] args) {

//        Calculation1("9 3 1 - 3 * + 10 2 / +");
        System.out.println(Calculation2("9 + ( 3 - 1 ) * 3 + 10 / 2"));
    }

    /**
     * 计算后缀表达式
     * @param inputString 9 3 1 - 3 * + 10 2 / + 以空格分隔
     */
    public static int Calculation1(String inputString){
        String[] input = inputString.split(" ");

        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < input.length; i++) {
            String s = input[i];
            if (isNumber(s))  //如果是数字，则入栈
                stack.push(Integer.valueOf(s));
            else {
                //遇到运算符，则从栈中弹出两个数字，进行运算
                int n1 = stack.pop();
                int n2 = stack.pop();
                int res = 0;
                switch (s){
                    case "+":res = n1 + n2;break;
                    case "-":res = n2 - n1;break;
                    case "*":res = n1 * n2;break;
                    case "/":res = n2 / n1;break;
                }
                stack.push(res);
            }
        }

        return stack.pop();
    }

    /**
     * 将中缀表达式转化为后缀表达式
     * @param string 9 + ( 3 - 1 ) * 3 + 10 / 2
     * @return
     */
    public static String Calculation2(String string){
        Stack<String> stack = new Stack();
        String[] chars = string.split(" ");
        String res = "";
        for (int i = 0; i < chars.length; i++) {
            String s = String.valueOf(chars[i]);
            if (isNumber(s)){
                if (res.length()==0)
                    res += s;
                else
                    res += " "+s;
            }else {
                if (s.equals("(")){
                    stack.push(s);
                }else {
                    if (s.equals(")")){
                        String t = "";
                        String s1 = "";
                        while (!(t = stack.pop()).equals("(")){
                             s1 += " "+t;
                        }
                        res += s1;
                    }else {
                        int priority = getPriority(s);
                        String s1 = "";
                        boolean flag = false;
                        while (!stack.empty()){
                            flag = false;
                            s1 = stack.pop();
                            if (s1.equals("(")){
//                                stack.push("(");
                                break;
                            }

                            if (getPriority(s1) >= priority){
                                res += " " + s1;
                                flag = true;
                            }
                        }
                        if (!s1.equals("") && !flag)
                            stack.push(s1);
                        stack.push(s);
                    }
                }


            }

        }

        while (!stack.empty()){
            res += " " + stack.pop();
        }


        return res;
    }


    //获取运算符的优先级
    public static int getPriority(String s){
        Map<String,Integer> map = new HashMap<>();
        map.put("+",0);
        map.put("-",0);
        map.put("*",1);
        map.put("/",1);
        map.put("(",2);
        map.put(")",2);


        return map.get(s);
    }

    public static boolean isNumber(String c){

        Pattern pattern = Pattern.compile("^(0|[1-9][0-9]*)$");
        Matcher matcher = pattern.matcher(c);
        boolean res = matcher.find();
        return res;
    }
}