表达式求值

 /**
     * @author tt
     * @Date Created in 2024/4/10 下午4:21
     */
    public static int solve(String s) {
        Set<String> symbol = Stream.of("+", "-", "*", "(", ")").collect(Collectors.toSet());

        Deque<String> symbolStack = new ArrayDeque<>();
        Deque<Integer> numberStack = new ArrayDeque<>();
        List<String> stringList = getStringList(s);
        for (String str : stringList) {
            if (!symbol.contains(str)) {  // 数字
                numberStack.push(Integer.valueOf(str));
            } else { // 符号
                switch (str) {
                    case "+":
                    case "-":
                        while ("*".equals(symbolStack.peek())) {
                            int opt2 = numberStack.poll();
                            int opt1 = numberStack.poll();
                            symbolStack.poll();
                            numberStack.push(opt1 * opt2);
                        }
                        symbolStack.push(str);
                        break;
                    case "*":
                    case "(":
                        symbolStack.push(str);
                        break;
                    case ")":
                        Deque<String> tempSymbolStack = new ArrayDeque<>();
                        Deque<Integer> tempNumberStack = new ArrayDeque<>();
                        while (!"(".equals(symbolStack.peek())) {
                            tempSymbolStack.addLast(symbolStack.poll());
                            tempNumberStack.addLast(numberStack.poll());
                        }
                        tempNumberStack.addLast(numberStack.poll());
                        symbolStack.poll();
                        while ("*".equals(tempSymbolStack.peek())) {
                            int opt2 = tempNumberStack.poll();
                            int opt1 = tempNumberStack.poll();
                            tempSymbolStack.poll();
                            tempNumberStack.push(opt1 * opt2);
                        }
                        while (!tempSymbolStack.isEmpty()) {
                            String currentSymbol = tempSymbolStack.pollLast();
                            int opt1 = tempNumberStack.pollLast();
                            int opt2 = tempNumberStack.pollLast();
                            tempNumberStack.addLast(compute(opt1, opt2, currentSymbol));
                        }
                        numberStack.push(tempNumberStack.poll());
                        break;
                }
            }
        }
        // 最后执行一次普通运算
        while ("*".equals(symbolStack.peek())) {
            int opt2 = numberStack.poll();
            int opt1 = numberStack.poll();
            symbolStack.poll();
            numberStack.push(opt1 * opt2);
        }
        while (!symbolStack.isEmpty()) {
            String currentSymbol = symbolStack.pollLast();
            int opt1 = numberStack.pollLast();
            int opt2 = numberStack.pollLast();
            numberStack.addLast(compute(opt1, opt2, currentSymbol));
        }
        return numberStack.peek();
    }

    private static int compute(int opt1, int opt2, String currentSymbol) {
        switch (currentSymbol) {
            case "*":
                return opt1 * opt2;
            case "+":
                return opt1 + opt2;
            case "-":
                return opt1 - opt2;
        }
        return 0;
    }


    /**
     * 拆解字符串
     *
     * @param s 原始字符串
     * @return 将数字和符号拆解
     * @author tt
     * @Date Created in 2024/4/10 下午4:22
     */
    private static List<String> getStringList(String s) {
        List<String> strList = new ArrayList<>();
        StringBuilder stringBuilder = new StringBuilder();
        Set<String> numberSet = Stream.of("1", "2", "3", "4", "5", "6", "7", "8", "9", "0").collect(Collectors.toSet());
        for (String str : s.split("")) {
            // 判断是否为数字
            if (numberSet.contains(str)) {
                stringBuilder.append(str);
            } else {
                if (stringBuilder.length() != 0) {
                    strList.add(stringBuilder.toString());
                    stringBuilder = new StringBuilder();
                }
                strList.add(str);
            }
        }
        if (stringBuilder.length() != 0) {
            strList.add(stringBuilder.toString());
        }
        return strList;
    }

HashMap<Character ,Integer> map=new HashMap<Character ,Integer>(){{
    put('+' ,1);
    put('-' ,1);
    put('*' ,2);
}};

public int solve (String s) {
    // write code here
    Stack<Character> s1=new Stack<>();
    Stack<Integer> s2=new Stack<>();
    s2.push(0);
    char[] cs=s.replaceAll(",","").toCharArray();

    for(int i=0;i<cs.length;i++){
        // 1、遇到左括号
        if(cs[i]=='('){
            s1.push('(');
        }else if(Character.isDigit(cs[i])){ //2、遇到数字
            int num=0;
            while(i<cs.length && Character.isDigit(cs[i])){
                num=num*10+(cs[i++]-'0');
            }
            i--;
            s2.push(num);
        }else if(cs[i]==')'){// 3、遇到右括号
            while(s1.peek()!='('){
                cacl(s1 ,s2);
            }
            s1.pop();
        }else{// 4、遇到计算符号
            if(i>0 && cs[i-1]=='('){ // 4.1 如果左括号后紧跟一个计算符号，需要在符号前加个0 ，便于进行计算
                s2.push(0);
            } // 4.2 符号优先级高的会先进行计算
            while(!s1.isEmpty() && s1.peek()!='(' && map.get(cs[i])<=map.get(s1.peek())){
                cacl(s1 ,s2);
            } // 4.3 处理完紧跟左括号和优先级计算，需要将当前的符号压栈
            s1.push(cs[i]);
        }
    }
    // 5、将没计算完的情况进行计算，如只有1+2
    while(!s1.isEmpty()){
        cacl(s1 ,s2);
    }
    return s2.pop();
}

public void cacl(Stack<Character> s1 ,Stack<Integer> s2){
    if(s1.size()<1 || s2.size()<2){
        return;
    }
    char c=s1.pop();
    int n=s2.pop() ,m=s2.pop();
    if(c=='+'){
        s2.push(m+n);
    }else if(c=='-'){
        s2.push(m-n);
    }else{
        s2.push(m*n);
    }
}

时间超时啊

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve (String s) {
        // write code here
        int result = 0;
        List<String> transList = transList(s);
        System.out.println(transList);
        List<String> reversePolish = reversePolish(transList);
        System.out.println(reversePolish);
        result = calculate(reversePolish);
        return result;
    }

    private int calculate(List<String> reversePolish) {
        // TODO
        Stack<String> temp = new Stack<>();
        reversePolish.stream().forEach(e-> {
            if (e.matches("//d")) {
                temp.add(e);
            } else {
                int num1 = Integer.parseInt(temp.pop());
                int num2 = Integer.parseInt(temp.pop());
                int res = calc(num1, num2, e);
                temp.add(res + "");
            }
        });
        return Integer.parseInt(temp.pop());
    }

    private int calc(int num1, int num2, String e) {
        // TODO
        int res = 0;
        switch (e) {
            case "+":
                res = num1 + num2;
                break;
            case "-":
                res = num1 - num2;
                break;
            case "*":
                res = num1 * num2;
                break;
            case "/":
                res = num1 / num2;
                break;
        }
        return res;
    }

    private List<String> reversePolish(List<String> transList) {
        // TODO
        List<String> res = new ArrayList<>(); // 队列，用于保存后缀表达式
        Stack<String> opt = new Stack<>(); //暂时保存运算符的栈
        transList.stream().forEach(e-> {
            if (e.matches("//d")) { // 正则表达式来判断，如果是数字，则直接入队；
                res.add(e);
            } else {
                if (e.equals("(")) { // 若是左括号，直接入运算符栈
                    opt.add("(");
                } else if (
                    e.equals(")")) { // 如果是右括号，则将运算符栈中的运算符出栈 并入队到表达式队列中
                    while (!opt.isEmpty() && !opt.peek().equals("(")) {
                        res.add(opt.pop());
                    }
                    opt.pop(); // 最后把左括号出栈;
                } else {
                    // 如过是四则运算符+ - * /,则先和运算符栈顶元素比较优先级,若优先级比栈顶的高则直接入栈，
                    // 否则将运算符栈出栈并入到表达式队列,直到优先级大于栈顶元素，再入栈
                    while (!opt.isEmpty() && getValue(opt.peek()) >= getValue(e)) {
                        res.add(opt.pop());
                    }
                    opt.add(e);
                }
            }
        });
        while (!opt.isEmpty()) {
            res.add(opt.pop());
        }
        return res;
    }

    private int getValue(String opt) {
        // TODO
        int reslut = 0;
        switch (opt) {
            case "+":
                reslut = 1;
                break;

            case "-":
                reslut = 1;
                break;

            case "*":
                reslut = 2;
                break;

            case "/":
                reslut = 2;
                break;
        }
        return reslut;
    }
    private List<String> transList(String s) {
        // TODO
        List<String> express = new ArrayList<>();
        int i = 0;
        String str; // 用于拼接多位数字
        while (i < s.length()) {
            char ch = s.charAt(i);
            if (ch < 48 || ch > 57) {
                express.add(ch + "");
            } else {
                str = "";
                while (i < s.length() && (s.charAt(i) >= 48 && s.charAt(i) <= 57)) {
                    str = str + s.charAt(i) + "";
                    i++;
                }
                express.add(str);
            }
        }
        return express;
    }


}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    // 存放操作数
    Stack<Integer> nums = new Stack<Integer>();
    // 存放运算符
    Stack<Character> ops = new Stack<Character>();
    // 维护运算符优先级,数字越大优先级越高
    HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    public int solve (String s) {
        // write code here
        map.put('+', 1);
        map.put('-', 1);
        map.put('*', 2);
        // 遍历表达式
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            // 遇到数字
            if (Character.isDigit(ch)) {
                int num = 0;
                int j = i;
                // 判断是否为多位数
                while (j < s.length() && Character.isDigit(s.charAt(j))) {
                    num = s.charAt(j++) - '0' + num * 10;
                }
                // 将数字加入操作数集
                nums.push(num);
                // 下轮循环i应该从数字的后一位开始，即j-1，因为while中j < s.length()时
                // j指向了数字的下一位，如果令i=j，则for过程i++时，i将从数字下下一位开始
                i = j - 1;
                // ops为空，运算符和左括号直接入栈
            }  else if (ops.size() == 0 && ch != ')') {
                ops.push(ch);
            }
            // 遇到左括号直接入栈
            else if (ch == '(') {
                ops.push(ch);
            }
            // 遇到右括号，则计算，运算符出栈（由eval完成），直到遇到栈顶为左括号，并舍弃左右括号。左括号前的运算符
            // 会在eval()中出栈
            else if (ch == ')') {
                while (ops.peek() != '(') {
                    eval();
                }
                ops.pop();
            }
            // 遇到运算符
            else {
                // 运算符栈不为空，且栈顶元素不为左括号且当前运算符优先级不大于栈顶运算符优先级，
                // 则对ops弹栈通过eval()进行运算，ops弹栈由eval计算过程中完成，计算直到栈顶的
                // 运算符优先级小于当前运算符优先级为止，并将当前运算符入栈
                while (ops.size() != 0 && ops.peek() != '(' && map.get(ops.peek()) >= map.get(ch)) {
                    eval();
                }
                ops.push(ch);
            }
        }
        // 栈中还有运算符时，循环运算至ops为空
        while (ops.size() != 0) {
            eval();
        }
        // 最后栈中只剩下计算结果，直接弹栈
        return nums.pop();
    }

// 计算
    public void eval() {
        int b = nums.pop();
        int a = nums.pop();
        char c = ops.pop();
        int res = 0;
        switch (c) {
            case '+':
                res = a + b;
                break;
            case '-':
                res = a - b;
                break;
            case '*':
                res = a * b;
                break;
        }
        // if(c=='+') res = a + b;
        // else if (c=='-') res = a - b;
        // else if (c=='*') res = a * b;
        nums.push(res);
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve (String s) {
        // write code here
        Map<Character,Integer> map = new  HashMap<Character,Integer> ();
        map.put('+',1);
        map.put('-',1);
        map.put('*',2);
        Stack<Integer> nums = new Stack<Integer>();
        Stack<Character> ops = new Stack<Character>();
        int num = s.length();
        char[] ss = s.toCharArray();
        for (int i = 0 ; i < num; i++) {
            char ch = ss[i];
            if (isNumber(ch)) {
                int temp = 0;
                int j = i;
                while (j < num && isNumber(ss[j])) {
                    temp = temp * 10 + (ss[j] - '0');
                    j++;
                }
                nums.push(temp);
                i = j - 1;
            } else if (ch == '(') {
                ops.push(ch);
            }else if(ch==')'){
                while(ops.peek()!='('){
                    calcu(nums,ops);
                }
                ops.pop();
            }else{
                while(!ops.isEmpty()&&ops.peek()!='('&&(map.get(ops.peek())>=map.get(ch))){
                    calcu(nums,ops);
                }
                ops.push(ch);
            }
        }
        while(!ops.isEmpty()){
            calcu(nums,ops);
        }
        return nums.pop();
    }
    public boolean isNumber (char a) {
        return Character.isDigit(a);
    }
    public void calcu (Stack<Integer> nums, Stack<Character> ops) {
        int num1 = nums.pop();
        int num2 = nums.pop();
        char op = ops.pop();
        if (op == '+') {
            nums.push(num1 + num2);
        } else if (op == '-') {
            nums.push(num2 - num1) ;
        } else if (op == '*') {
            nums.push(num1 * num2);
        }
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve (String s) {
        char[] chars = s.toCharArray();
        Stack<Integer> numStack = new Stack<>();//运算数
        Stack<Character> operatorStack = new Stack<>();//运算符
        for(int i=0;i<chars.length;i++){
            char curchar = chars[i];
            if(isDight(curchar)){//数字
                int num = 0;
                while(i<chars.length && isDight(chars[i])){//循环读取当前数字(多位)
                    num = num*10+(chars[i]-'0');
                    i++;
                }
                i--;//将i-1当前指针指向当前数的最后一位
                numStack.push(num);//数字入栈
            }else if(curchar=='('){//'('入栈
                operatorStack.push(curchar);
            }else if(curchar==')'){//遇到')'开始运算()内的表达式
                while(operatorStack.peek()!='('){//多个()嵌套处理
                    operate(numStack,operatorStack);
                }
                operatorStack.pop();// '('出栈
            }else {
                while(!operatorStack.isEmpty() && getPriority(curchar) <= getPriority(operatorStack.peek()) ){//当前优先级<栈内优先级
                    operate(numStack,operatorStack);//提取表达式计算
                }
                operatorStack.push(curchar);//当前运算符入栈
            }
        }

        while(!operatorStack.isEmpty()){//运算符不为空,继续计算
            operate(numStack,operatorStack);
        }
        return numStack.pop();//返回最后结果

    }

    private int getPriority(Character character) {//优先级
        if(character == '+' || character=='-'){
            return 1;
        }else if(character =='*' || character =='/'){
            return 2;
        }
        return -1;//遇见'()'的优先级
    }

    private void operate(Stack<Integer> numStack, Stack<Character> operatorStack) {//提取当前表达式计算
        char operator = operatorStack.pop();
        int rightnum = numStack.pop();
        int leftnum = numStack.pop();
        int newnum = compute(leftnum,operator,rightnum);//计算
        numStack.push(newnum);//添加运算结果入栈
    }

    private int compute(int a, char operator, int b) {
        switch (operator){
            case '+': return a + b;
            case '-': return a-b;
            case '*': return a*b;
            case '/': 
                if(b==0){
                    throw new RuntimeException("cannot not divide 0!");
                }
                return a/b;
            default :
                throw new UnsupportedOperationException();

        }
    }

    private boolean isDight(char curchar) {
        return curchar>='0' && curchar <='9';
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve1 (char ch, int a, int b) {
        switch (ch) {
            case '+':
                return b + a;
            case '-':
                return b - a;
            case '*':
                return b * a;
        }
        return 0;
    }

    public int solve (String s) {
        // write code here
        Stack<Character> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        char ch;
        int i = 0;
        String s1 = "";
        short flag1 = 0;
        short flag2 = 0;
        while (i < s.length()) {
            ch = s.charAt(i);
            if (!stack1.empty() && stack1.peek() == '*'){
                flag1 = 1;
            }
            if ( ch == ')') {
                while (stack1.peek() != '(') {
                    int eg = solve1(stack1.pop(), stack2.pop(), stack2.pop());
                    stack2.push(eg);
                }
                stack1.pop();
                    if (flag1 == 1 && flag2 >0){
                    flag2--;
                }
                i++;
            } else {
                s1 = "";
                while (ch != '+'  && ch != '*' && ch != '-' && ch != '(' && ch != ')') {
                    if (i < s.length() - 1) {
                        s1 += ch;
                        ch = s.charAt(++i);
                    } else if (i == s.length() - 1) {
                        s1 += ch;
                        i++;
                    } 
                    if (i == s.length()) {
                        break;
                    }
                }
                if (s1 != "") {
                    stack2.push(Integer.parseInt(s1));
                }
                if (flag1 == 1 && ch == '(' ){
                    flag2++;
                }
                if (flag1 == 1 && flag2 == 0 && !stack1.empty()){
                    int eg = solve1(stack1.pop(), stack2.pop(), stack2.pop());
                    stack2.push(eg);
                    flag1 = 0;
                }

                if (ch == '+' || ch == '*' || ch == '(' || ch == '-') {
                    stack1.push(ch);
                    i++;
                }
            }
        }
        while (!stack1.empty() ) {
            char eg1 = stack1.pop();
            if (!stack1.empty() && stack1.peek() == '-') {
                if (eg1 == '-')
                eg1 = '+';
                else
                eg1 = '-';
            }
            int eg2 = solve1(eg1, stack2.pop(), stack2.pop());
            stack2.push(eg2);
        }
        return stack2.pop();
    }

}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve (String s) {
        // write code here

        return func(s, 0, s.length() - 1);
    }

    public int func(String s, int startIndex, int endIndex) {
        Stack<Integer> st = new Stack<>();

        char op = '+';
        for (int i = startIndex; i <= endIndex; i++) {
            int num = 0;
            boolean isNum = false;
            if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                isNum = true;
                num = s.charAt(i) - '0';

                while (i+1 <= endIndex && s.charAt(i+1) >= '0' && s.charAt(i+1) <= '9') {
                    i++;
                    num = num * 10 + (s.charAt(i) - '0');
                }
            }

            if (isNum && op == '+') {
                st.push(num);
            } 
            else if (isNum && op == '-') {
                st.push(0 - num);
            }
            else if (isNum && op == '*') {
                int preNum = st.pop();
                st.push(preNum * num);
            }
            else if (!isNum && s.charAt(i) == '(') {
                int leftCount = 0;
                int nextStart = i + 1;
                i++;
                while (i <= s.length() - 1 && (s.charAt(i) != ')' || leftCount != 0)) {
                    if (s.charAt(i) == '(') {
                        leftCount++;
                    }
                    else if (s.charAt(i) == ')') {
                        leftCount--;
                    }
                    i++;
                }
                int nextEnd = i - 1;
                num = func(s, nextStart, nextEnd);
                if (op == '+') {
                    st.push(num);
                }
                else if (op == '-') {
                    st.push(0 - num);
                }
                else if (op == '*') {
                    int preNum = st.pop();
                    st.push(preNum * num);
                }
            }
            else if (!isNum && (s.charAt(i) == '+' || s.charAt(i) == '-' || s.charAt(i) == '*')) {
                op = s.charAt(i);
            }
        }

        int ans = 0;
        while (!st.isEmpty()) {
            ans += st.pop();
        }

        return ans;
    }
}