//整體思路：
//https://blog.csdn.net/Amentos/article/details/127182926?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522171747048816800182783010%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=171747048816800182783010&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-127182926-null-null.142^v100^pc_search_result_base3&utm_term=%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F&spm=1018.2226.3001.4187
//上述博客有中綴表達(dá)式和后綴表達(dá)式的講解，可以了解具體概念，并且如何計(jì)算后綴表達(dá)式也有相關(guān)說(shuō)明
//下面開(kāi)始傻瓜式代碼，保證你一定看的懂！
import java.util.*;

public class Solution {

    public Map<Character, Integer> map = new HashMap<>();
    
    public void operateMap(){
        map.put('+', 1);
        map.put('-', 1);
        map.put('*', 2);
        map.put('/', 2);
        map.put('(', 0);
    }
    
    public int solve (String s) {
        if (s == ""){
            return 0;
        }

        operateMap();
        return calculate(houzhui(s));
    }
    

    //中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式
    public String houzhui(String s){
        //用來(lái)臨時(shí)存放運(yùn)算符
        Stack<Character> opt = new Stack<>();
        //用來(lái)存放后綴表達(dá)式
        String res = "";

        for(int i = 0; i < s.length(); i++){
            //將遍歷的每一個(gè)字符都取出來(lái)
            char c = s.charAt(i);
            if (c == ' '){
                continue;
            }
            //如果是數(shù)字
            if (c >= '0' && c <= '9'){
                while(i < s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9'){
                    res += s.charAt(i);
                    i++;
                }
                res += "#";
                i--;
            }
            //左括號(hào)直接入棧
            else if (c == '('){
                opt.add(c);
            }
            //右括號(hào)依次從opt棧頂退運(yùn)算符，直至碰到左括號(hào)
            else if (c == ')'){
                while(opt.size() != 0 && opt.peek() != '('){
                    res += opt.pop();
                }
                //這里暫時(shí)不考慮違法操作
                //將左括號(hào)彈出
                opt.pop();
            }
            //運(yùn)算符分情況討論
            else{
                //首先討論負(fù)數(shù)的符號(hào)問(wèn)題，需要將負(fù)號(hào)和運(yùn)算符的減號(hào)邏輯上劃等號(hào)
                //負(fù)號(hào)單獨(dú)出現(xiàn)的情況只有這兩種，要么開(kāi)頭要么和左括號(hào)連在一起，不考慮違法操作,
                //例如：5*-5，都認(rèn)為符合正常書(shū)寫(xiě)規(guī)范，類(lèi)似5*(-5)
                if (c == '-' && (i == 0 || s.charAt(i - 1) == '(')){
                    res += "0";
                    res += "#";
                    //此時(shí)的負(fù)數(shù)所帶的負(fù)號(hào)要想邏輯上和減號(hào)劃等號(hào)，需要它的負(fù)號(hào)優(yōu)先級(jí)最大，直接入棧
                    //5 / (-6 * 3)
                    //5 / ((0 - 6) * 3)
                    opt.add(c);
                    continue;
                }
                //運(yùn)算符棧為空 或 棧頂是左括號(hào) 或 當(dāng)前運(yùn)算符的優(yōu)先級(jí)大于棧頂運(yùn)算符的優(yōu)先級(jí)，當(dāng)前運(yùn)算符直接入棧
                if (opt.size() == 0 || opt.peek() == '(' || map.get(c) > map.get(opt.peek())){
                    opt.add(c);
                }
                //當(dāng)當(dāng)前運(yùn)算符優(yōu)先級(jí)小于等于棧頂運(yùn)算符優(yōu)先級(jí)時(shí)，一直彈出棧頂運(yùn)算符直至當(dāng)前運(yùn)算符優(yōu)先級(jí)大于棧頂運(yùn)算符優(yōu)先級(jí)或者棧為空
                else{
                    res += Character.toString(opt.pop());
                    //即便彈出之后，當(dāng)前棧頂符號(hào)是左括號(hào)也沒(méi)有關(guān)系，根據(jù)全局變量map宏定義：左括號(hào)的優(yōu)先級(jí)最小
                    while (opt.size() != 0 && map.get(c) <= map.get(opt.peek())){
                        res += opt.pop();
                    }
                    opt.add(c);
                }
            }
        }

        while(opt.size() != 0){
            res += opt.pop();
        }

        return res;
    }
    
    //計(jì)算后綴表達(dá)式
    public int calculate(String s){
        //用來(lái)臨時(shí)存放操作數(shù)
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if (s.charAt(i) >= '0' && s.charAt(i) <= '9'){
                int sum = 0;
                while(s.charAt(i) != '#'){
                    sum = sum * 10 + s.charAt(i) - '0';
                    i++;
                }
                stack.add(sum);
            }
            else{
                if (c == '+'){
                    int hou = stack.pop();
                    int qian = stack.pop();
                    stack.add(qian + hou);
                }
			    //注意運(yùn)算順序
                else if (c == '-'){
                    int hou = stack.pop();
                    int qian = stack.pop();
                    stack.add(qian - hou);
                }
                else if (c == '*'){
                    int hou = stack.pop();
                    int qian = stack.pop();
                    stack.add(qian * hou);
                }
                else {
                    int hou = stack.pop();
                    int qian = stack.pop();
                    //此時(shí)先暫且不考慮除0的操作，畢竟此題并沒(méi)有把除法運(yùn)算包含進(jìn)來(lái)
				    //后續(xù)題目如果有除法操作，可以選擇進(jìn)行if判斷，return題目要求的不合法的默認(rèn)值
                    stack.add(qian / hou);
                }
            }
        }
        return stack.pop();
    }
}