HJ54. 表达式求值

刷题

题目：给定一个字符串描述的算术表达式，计算出结果值。
输入字符串长度不超过 100 ，合法的字符包括 ”+, -, *, /, (, )”，”0-9” 。

数据范围：运算过程中和最终结果均满足 |val|<2^31-1，即只进行整型运算，确保输入的表达式合法

输入描述：输入算术表达式
输出描述：计算出结果值

示例：

输入：400+5
输出：405

类似的题目还有 HJ50. 四则运算

import java.util.*;
import javax.script.*;
public class Main {
    public static void main(String[] args) throws ScriptException {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String s = sc.nextLine()
                .replace("[","(")
                .replace("]",")")
                .replace("{","(")
                .replace("}",")");
            System.out.println(eval1(s));
            System.out.println(eval2(s));
        }
    }
    //方法一
    public static int eval1(String s) {
        char ops = '+';
        Stack<Integer> stack = new Stack<>();
        for(int i=0; i<s.length(); i++){
            char c = s.charAt(i);
            if(c == ' ') continue;
            if(Character.isDigit(c)){
                int num = 0;
                while(i<s.length() && Character.isDigit(s.charAt(i))){
                    num = num*10 + s.charAt(i) - '0';
                    i++;
                }
                i--;
                if(ops == '+') stack.push(num);
                else if(ops == '-') stack.push(-num);
                else if(ops == '*') stack.push(stack.pop()*num);
                else if(ops == '/') stack.push(stack.pop()/num);
            } else if (c=='+' || c=='-' || c=='*' || c=='/'){
                ops = c;
            } else if (c == '('){
                int left = i;//左括号当前位置的索引
                int right = i+1;
                int count = 1;//括号层级计数
                while(right<s.length() && count>0){
                    if(s.charAt(right)=='(') count++;
                    else if(s.charAt(right)==')') count--;
                    right++;
                }
                i = right-1;
                //取()里面的表达式继续计算
                int num = eval1(s.substring(left+1, right-1));
                if(ops == '+') stack.push(num);
                else if (ops == '-') stack.push(-num);
                else if (ops == '*') stack.push(stack.pop()*num);
                else if (ops == '/') stack.push(stack.pop()/num);
            }
        }
        int ans = 0;
        while(!stack.isEmpty()) ans+=stack.pop();
        return ans;
    }
    //方法二：使用java8自带的js引擎，但有时并不满足时间和内存限制
    public static int eval2(String s) throws ScriptException {
        ScriptEngine scriptEngine = new ScriptEngineManager().getEngineByName("nashorn");
        return scriptEngine.eval(s);
    }
}