NC137 表达式求值

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve (String s) {
        Stack<Character> ops = new Stack<Character>();
        Stack<Integer> nums = new Stack<>();
        char[] ch = s.toCharArray();
        for(int i=0;i<ch.length;i++){
            if(ch[i] == '(' || ch[i] == '*' ) ops.push(ch[i]);
            else if(IsNum(ch[i])) {
                String temp = "";
                while(i<ch.length && IsNum(ch[i])) temp = temp + ch[i++];
                i--;
                nums.push(Integer.parseInt(temp));
            }
            else if(ch[i] == '+' || ch[i] == '-' ){
                while(!ops.empty() && (ops.peek()=='*' ||ops.peek()=='+' ||ops.peek()=='-')){
                    int num1 = nums.pop();
                    int num2 = nums.pop();
                    int res = calculate(ops.pop(),num1,num2);
                    nums.push(res);
                }
                ops.push(ch[i]);
            }
            else if(ch[i] == ')'){
                while(!ops.empty() && ops.peek() != '('){
                    int num1 = nums.pop();
                    int num2 = nums.pop();
                    int res = calculate(ops.pop(),num1,num2);
                    nums.push(res);
                }
                ops.pop();
            }
        }
        int res = 0;
        while(!ops.empty()){
            int num1 = nums.pop();
            int num2 = nums.pop();
            int temp_res = calculate(ops.pop(),num1,num2);
            nums.push(temp_res);
        }
        return nums.pop();
    }

    public int calculate(char op, int b, int a){
        if(op == '+') return a+b;
        if(op == '-') return a-b;
        if(op == '*') return a*b;
        return 0;
    }

    public boolean IsNum(char num){
        if('0'<= num && num<='9') return true;
        else return false;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve (String s) {
        if(s.length()<2){return (int)s.charAt(0);}
        Stack<Character> ops = new Stack<Character>(); // 存放运算符
        Stack<Integer> num = new Stack<Integer>();  // 存放数

        num.push(0);

        for(int i = 0 ; i<s.length();){ // 从头扫描到尾
            if(s.charAt(i) == '('){ // 遇到直接进栈 无任何操作
                ops.push(s.charAt(i++));
            }
            else if(s.charAt(i) == ')'){ // 优先级最高 计算括号里的内容 把结果放入num
                while(ops.peek()!='('){
                    char op = ops.pop();
                    int numb = num.pop();
                    int numa = num.pop();
                    num.push(calculate(op,numa,numb));
                }
                ops.pop();// ‘(’最后一个判断并没有在运算符栈中弹出 这里需要补上
                i++;
            }else if(s.charAt(i) == '*'){ // 乘法直接入栈就行 他的优先级第二高 不用管栈里是什么运算， 
//如果算上除法 其实是有顺序的 遇到同等优先级的 先算之前的，但是乘法具有交换性 所以
                ops.push('*');
                i++;
            }else if(s.charAt(i) == '+' || s.charAt(i) == '-'){
// 需要判断 如果里面优先级低于 则入栈 大于等于则先计算里面的
                if(ops.isEmpty()){
                    ops.push(s.charAt(i++));
                }
                else if( ops.peek() == '*' || ops.peek() == '-' || ops.peek() == '+' ){
                    char op = ops.pop();
                    int numb= num.pop();
                    int numa = num.pop();
                    num.push(calculate(op,numa,numb));
                }
                else ops.push(s.charAt(i++));
            }else{//处理数字
                int numa = 0;
                while(i<s.length() && IsNum(s.charAt(i))){
                    numa = 10*numa + s.charAt(i++) - '0';
                }
                num.push(numa);
            }
        }
        int res = 0;
        //如果还有没计算完的部分 继续计算
        while(!ops.isEmpty()){
            char op = ops.pop();
            int numb = num.pop();
            int numa = num.pop();
            res = res + num.push(calculate(op,numa,numb));
        }


        return res;
    }

    public int calculate(char op, int a, int b){
        if(op == '+') return a+b;
        if(op == '-') return a-b;
        if(op == '*') return a*b;
        return 0;
    }

    public boolean IsNum(char num){
        if('0'<= num && num<='9') return true;
        else return false;
    }
}

化简版

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve (String s) {
        if(s.length()<2){return (int)s.charAt(0);}
        Stack<Character> ops = new Stack<Character>();
        Stack<Integer> num = new Stack<Integer>();

        num.push(0);

        for(int i = 0 ; i<s.length();){
            if(s.charAt(i) == '('){
                ops.push(s.charAt(i++));
            }
            else if(s.charAt(i) == ')'){
                while(ops.peek()!='('){
                    num.push(calculate(ops.pop(), num.pop(),num.pop()));
                }
                ops.pop();
                i++;
            }else if(s.charAt(i) == '*'){
                ops.push('*');
                i++;
            }else if(s.charAt(i) == '+' || s.charAt(i) == '-'){
                if(ops.isEmpty()){
                    ops.push(s.charAt(i++));
                }
                else if( ops.peek() == '*' || ops.peek() == '-' || ops.peek() == '+' ){
                    num.push(calculate(ops.pop(), num.pop(),num.pop()));
                }
                else ops.push(s.charAt(i++));
            }else{
                int numa = 0;
                while(i<s.length() && IsNum(s.charAt(i))){
                    numa = 10*numa + s.charAt(i++) - '0';
                }
                num.push(numa);
            }
        }
        int res = 0;

        while(!ops.isEmpty()){
            res = res + num.push(calculate(ops.pop(), num.pop(),num.pop()));
        }


        return res;
    }

    public int calculate(char op, int b, int a){
        if(op == '+') return a+b;
        if(op == '-') return a-b;
        if(op == '*') return a*b;
        return 0;
    }

    public boolean IsNum(char num){
        if('0'<= num && num<='9') return true;
        else return false;
    }
}