前缀、后缀表达式

前缀表达式计算方式：

• 从左至右扫描，将6、5、4、3压入堆栈以‘- × + 3 4 5 6’为例
• 遇到运算符，弹出栈顶3，4（栈顶及次顶元素），计算3+4 的值 将7再入栈
• 接下来是× ，弹出7 、5，计算7×5，将35入栈
• 最后是-运算符，计算出35-6，即结果
  后缀表达式计算方式：
• 从左至右扫描，遇到数字时，将数字压入栈，遇到运算符时弹出栈顶两个元素，并作运算，重复上述，直到表达式右端。
• 以‘34+5×6-’即（3+4）*5-6为例，从左到右扫描，将3、4入栈，遇到+弹出4（栈顶）和3（次顶），计算3+4的值，将7入栈
• 5入栈
• 接下来是×，将5和7出栈，并计算 ，35 入栈，
• 6入栈

• 最后是- 计算35-6，得29
  中缀转后缀表达式方法：

  

import java.util.*;

/**
 * @program: data_structure
 * @description:中缀转后缀
 * @author: wei
 * @create: 2021-07-09 22:50
 **/
public class infix {
    public static void main(String[] args) {
        String s = "100-2*(3+4)";
        List<String> ls = fixToList(s);
        System.out.println(ls);
        List<String> l = infixToSuffix(ls);
        System.out.println(l);
        System.out.println(cal(l));
    }

    public static List<String> fixToList(String s) {
        List<String> ls = new ArrayList<String>();
        char c;
        String ss;
        int i = 0;
        do {
            if (s.charAt(i) < 48 || s.charAt(i) > 57) {
                ls.add(s.charAt(i) + "");
                i++;
            } else {
                ss = "";
                while (i < s.length() && s.charAt(i) >= 48 && s.charAt(i) <= 57) {
                    ss = ss + s.charAt(i);
                    i++;
                }
                ls.add(ss);
            }
        } while (i < s.length());
        return ls;
    }

    public static List<String> infixToSuffix(List<String> ls) {
        Stack<String> temp = new Stack<String>();
        List<String> s2 = new ArrayList<String>();

        int l = ls.size();
        for(String s: ls){
            if(s.matches("\d+")){
                s2.add(s);
                System.out.println(s2);
            }
            else{
                if(temp.empty()||s.equals("(")||temp.peek().equals("(")){
                    temp.push (s);
                }else if(s.equals(")")){
                    while(!temp.peek().equals("(")){
                        s2.add(temp.pop());
                    }
                    temp.pop();
                }
                else{
                    if (s.equals("+")||s.equals("-")) {
                        while (!temp.empty() && (!temp.peek().equals("("))) {
                            s2.add(temp.pop());
                        }
                        temp.push(s);
                    }
                    if (s.equals("*")||s.equals("/")){
                        while((!temp.empty()) && (temp.peek().equals("*")||temp.peek().equals("/"))){
                            s2.add(temp.pop());
                        }
                        temp.push(s);
                    }
                }
            }
        }
        while(!temp.empty()){
            s2.add(temp.pop());
        }

        return s2;
    }
    public static int cal(List<String> ls){
        Stack<Integer> stack = new Stack<Integer>();
        for(String s: ls){
            if (s.matches("\d+")){
                stack.push(Integer.parseInt(s));
            }
            else{
                int num2 = stack.pop();
                int num1 = stack.pop();
                int result = 0;
                if(s.equals("+")){
                    result = num1 + num2;
                }
                if(s.equals("-")){
                    result = num1 - num2;
                }
                if(s.equals("*")){
                    result = num1 * num2;
                }
                if(s.equals("/")){
                    result = num1 / num2;
                }
                stack.push(result);
            }
        }
        return stack.pop();
    }
}