2019计算机能力挑战赛Java题目5

题目

给定一个只包含0-9、+、*的合法数学表达式（长度<1000），规定加号‘+”的优先级高于乘号*”，请输出计算结果。输入说明：合法的数学表达式
输出说明：输出表达式的计算结果
输入样例：12*3+12*2输出样例：360

思路分析

本题本质上是一个简化版的四则运算问题。我们可以使用栈这一数据结构来解决。但是本题的难点是参与运算的数字并不只是10以内，这无疑加大了题目的难度。在本题中我使用StringBuffer来拼接字符串，将10以上的数字进行拼接处理。下面是解决本题的完整代码。

代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

public class Main14 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String string = scanner.nextLine();
        List<String> str = getTempStr(string);
        Integer result = getFinalResult(str);
        System.out.println(result);
        scanner.close();
    }

    /**
     * @MethodName: getFinalResult
     * @date: 2020/11/27 20:43
     * @author 索半斤
     * @Description: 根据后缀表达式获取算式的最终结果
     * 转换过程为：
     *          1、遍历后缀表达式，如果为数字则入栈
     *          2、如果为符号则将栈顶的两个元素出栈并进行操作
     *          3、将2中的计算结果入栈
     */
    private static Integer getFinalResult(List<String> list) {
        Stack<Integer> stack = new Stack<>();
        for (String s : list) {
            if (isNum(s) || s.length() > 1){
                stack.push(stringToInteger(s));
            }else {
                if (s.equals("+")) {
                    Integer  num1 = stack.pop();
                    Integer  num2 = stack.pop();
                    stack.push(num1 + num2);
                } else if (s.equals("*")) {
                    Integer num1 = stack.pop();
                    Integer num2 = stack.pop();
                    stack.push(num1 * num2);
                }
            }
        }
        return stack.pop();
    }

    private static Integer stringToInteger(String s){
        return Integer.parseInt(s);
    }
    /**
     * @MethodName: getTempStr
     * @date: 2020/11/27 20:20
     * @author 索半斤
     * @Description: 将中缀表达式转换为后缀表达式
     * 转换过程：
     *         1、遍历字符串，判断是否为数字
     *         2、如果为数字直接存入List中
     *         3、如果为符号则判断优先级，栈为空时无论任何符号都直接入栈
     *         4、当栈不为空时，如果栈中的元素优先级较高则栈中符号出栈，并将此时的符号入栈
     *         5、最后遍历栈，将余下的符号依次出栈
     */
    private static List<String> getTempStr(String string){
        Stack<String> stack = new Stack<>();
        List<String> list = new ArrayList<>(); //存放后缀表达式
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < string.length(); i++) {
            String temp = string.substring(i,i+1);
            if (i == string.length() - 1 && isNum(temp)){
                list.add(temp);
                continue;
            }
            if (isNum(temp)){
                sb.append(temp);
            }else{
                if (sb.length() > 0){
                    list.add(sb.toString());
                    sb = new StringBuffer();
                }
                if (temp.equals("*")){
                    if (stack.isEmpty()){
                        stack.push("*");
                    }else {
                        String peek = stack.peek();
                        if (peek.equals("+")) {
                            list.add(stack.pop());
                            stack.push("*");
                        } else {
                            stack.push(temp);
                        }
                    }
                } else if (temp.equals("+")){
                   stack.push("+");
                }
            }
        }
        while(!stack.isEmpty()){
            list.add(stack.pop());
        }
        return list;
    }

    /**
     * @MethodName: isNum
     * @date: 2020/11/27 20:49
     * @author 索半斤
     * @Description: 判断字符串是否是0-9的整数
     */
    private static boolean isNum(String string){
        return string.matches("[0-9]");
    }
}