牛客网：表达式求值(Java实现)

题目描述

给定一个字符串描述的算术表达式，计算出结果值。输入字符串长度不超过100，合法的字符包括”+, -, *, /, (, )”，”0-9”，字符串内容的合法性及表达式语法的合法性由做题者检查。本题目只涉及整型计算。

输入描述:

输入算术表达式

输出描述:

计算出结果值

关键解题思路：

1 读取一行输入String s，依次读取。若s[i]不是数字则将s的subString(index,i)截取转为整型操作数存放stk_int栈中。

2 判断当前s[i]存放的操作符与当前stk_str栈中的栈顶元素优先级大小。

3 若优先级比栈顶元素高，则入栈；否则，返回两个操作数与栈顶操作符运算后的结果并压入操作数栈。

4 遇到括号时需单独考虑，若遇到左括号，则入栈同时压入一个#；若遇到右括号，则进行两个操作数与栈顶操作符运算，直到遇到左括号。

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
//定义运算符及对应优先级
class OP{
    char c;
    int num;
    public OP(char c,int num){
        this.c = c;
        this.num = num;
    }
};
public class Main{
    //判断运算符优先级，c1 > c2则返回true
    public static boolean judge(char c1,char c2){
        OP op[] = new OP[7];
        char cf[] = {#,+,-,*,/,(,)};
        for(int i= 0 ;i<7;i++) {
            //System.out.println(cf[i]);
            op[i] = new OP(cf[i],i);
        }
        int num1 = 0,num2 = 0;
        for(int i = 0;i<7;i++){
            if(op[i].c == c1)
                num1 = i;
            if(op[i].c == c2)
                num2 = i;
        }
        if(op[num1].num > op[num2].num)
            return true;
        return false;
    }
    //根据运算符对操作数求值
    public static int option(int t1,int t2,char c){
        if(c == +)
            return t1 + t2;
        else if(c == -)
            return t2 - t1;
        else if(c == *)
            return t1 * t2;
        else
            return t2 / t1;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();//读入表达式
        ArrayList<Character> arr = new ArrayList<>();//拼接操作数
        Stack<Integer> stk_int = new Stack<>();//存放操作数
        Stack<Character> stk_str = new Stack<>();//存放操作符
        //数据存入栈中
        int index = 0;
        stk_str.push(#);
        for(int i = 0;i<s.length();i++){
            if(s.charAt(i) < 0 || s.charAt(i) > 9){
                if(index != i)
                    stk_int.push(Integer.parseInt(s.substring(index,i)));
                index = i+1;
                boolean b = false;
                while(b == false){
                    if (judge(s.charAt(i),stk_str.peek())){
                        stk_str.push(s.charAt(i));
                        if(stk_str.peek() == ( )
                            stk_str.push(#);
                        if( stk_str.peek() == )){
                            stk_str.pop();
                            while(stk_str.peek()!=#){      
                                stk_int.push(option(stk_int.pop(),stk_int.pop(),stk_str.pop()));
                            }
                            stk_str.pop();
                            stk_str.pop();
                        }
                        b = true;
                    }else{
                        stk_int.push(option(stk_int.pop(),stk_int.pop(),stk_str.pop()));
                    }
                }
            }
            if(index != s.length() && i == s.length()-1)
                stk_int.push(Integer.parseInt(s.substring(index,s.length())));
        }
        while(!stk_int.isEmpty() && stk_str.peek()!= #){
            stk_int.push(option(stk_int.pop(),stk_int.pop(),stk_str.pop()));
        }
        //判断运算后栈长度，用以判定表达式是否合法
        if(stk_str.peek()!=#)
            System.out.println("-1");
        else
            System.out.println(stk_int.pop());
    }
}