[编程|30分] 计算器

时间限制：C/C++ 1秒，其他语言 2秒
空间限制：C/C++ 40960K，其他语言 81920K

题目描述

输入为一个算数表达式的字符串。输出它经过计算之后的结果。如果该字符串不满足算数表达式则输出字符串Error。

注意：

1. 输入中的数只有非负整数。小数、负数等均需要输出Error。

2. 需要支持运算符加、减、乘以及括号。

3. 运算符的优先级为：括号>加=减>乘。

4. 支持数与操作符、操作符与操作符之间有任意空格。

5. 输入和运算过程中不需要考虑整数溢出，用32位的int即可。

输入描述:

输入1：123
输入2：1 23
输入3：1 + 2 3
输入4：1+(23)

输出描述:

输出1：123
输出2：Error
输出3：9
输出4：7

示例1

输入

1 + 2 3 - (45)

输出

-51

说明

1 + 2 3 - (45) => 1 + 2 3 - 20 => 3 3 - 20 => 3 * -17 => -51

package paypal.demo2;
import java.util.Scanner;
import java.util.Stack;
/**
 * 计算器
 */
public class Main {
    public static void main(String args[]) {
        Main cal = new Main();
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String numStr = sc.nextLine(); // 获得算式
            cal.caculate(numStr); // 计算算式的结果
        }
    }
    /**
     * 数字栈：用于存储表达式中的各个数字
     */
    private Stack numberStack = null;
    /**
     * 符号栈：用于存储运算符和括号
     */
    private Stack symbolStack = null;
    /**
     * 解析并计算四则运算表达式(含括号)，返回计算结果
     *
     * @param numStr 算术表达式(含括号)
     */
    public void caculate(String numStr) {
        numStr = removeStrSpace(numStr); // 去除空格
        // 如果算术表达式尾部没有‘=’号，则在尾部添加‘=’，表示结束符
        if (numStr.length() > 1 && !"=".equals(numStr.charAt(numStr.length() - 1) + "")) {
            numStr += "=";
        }
        // 检查表达式是否合法
        if (!isStandard(numStr)) {
            System.out.println("Error");
            return;
        }
        // 初始化栈
        numberStack = new Stack();
        symbolStack = new Stack();
        // 用于缓存数字，因为数字可能是多位的
        StringBuffer temp = new StringBuffer();
        // 从表达式的第一个字符开始处理
        for (int i = 0; i < numStr.length(); i++) {
            char ch = numStr.charAt(i); // 获取一个字符
            if (isNumber(ch)) { // 若当前字符是数字
                temp.append(ch); // 加入到数字缓存中
            } else { // 非数字的情况
                String tempStr = temp.toString(); // 将数字缓存转为字符串
                if (!tempStr.isEmpty()) {
                    int num = Integer.parseInt(tempStr); // 将数字字符串转为长整型数
                    numberStack.push(num); // 将数字压栈
                    temp = new StringBuffer(); // 重置数字缓存
                }
                // 判断运算符的优先级，若当前优先级低于栈顶的优先级，则先把计算前面计算出来
                while (!comparePri(ch) && !symbolStack.empty()) {
                    int b = numberStack.pop(); // 出栈，取出数字，后进先出
                    int a = numberStack.pop();
                    // 取出运算符进行相应运算，并把结果压栈进行下一次运算
                    switch (symbolStack.pop()) {
                        case '+':
                            numberStack.push(a + b);
                            break;
                        case '-':
                            numberStack.push(a - b);
                            break;
                        case '*':
                            numberStack.push(a * b);
                            break;
                        case '/':
                            numberStack.push(a / b);
                            break;
                        default:
                            break;
                    }
                } // while循环结束
                if (ch != '=') {
                    symbolStack.push(new Character(ch)); // 符号入栈
                    if (ch == ')') { // 去括号
                        symbolStack.pop();
                        symbolStack.pop();
                    }
                }
            }
        } // for循环结束
        System.out.println(numberStack.pop());
        return;
    }
    /**
     * 去除字符串中的所有空格
     */
    private String removeStrSpace(String str) {
        return str != null ? str.replaceAll(" ", "") : "";
    }
    /**
     * 检查算术表达式的基本合法性，符合返回true，否则false
     */
    private boolean isStandard(String numStr) {
        if (numStr == null || numStr.isEmpty()) // 表达式不能为空
            return false;
        Stack stack = new Stack(); // 用来保存括号，检查左右括号是否匹配
        boolean b = false; // 用来标记'='符号是否存在多个
        for (int i = 0; i < numStr.length(); i++) {
            char n = numStr.charAt(i);
            // 判断字符是否合法
            if (!(isNumber(n) || "(".equals(n + "") || ")".equals(n + "")
                    || "+".equals(n + "") || "-".equals(n + "")
                    || "*".equals(n + "") || "=".equals(n + ""))) {
                return false;
            }
            // 将左括号压栈，用来给后面的右括号进行匹配
            if ("(".equals(n + "")) {
                stack.push(n);
            }
            if (")".equals(n + "")) { // 匹配括号
                if (stack.isEmpty() || !"(".equals((char) stack.pop() + "")) // 括号是否匹配
                    return false;
            }
            // 检查是否有多个'='号
            if ("=".equals(n + "")) {
                if (b)
                    return false;
                b = true;
            }
        }
        // 可能会有缺少右括号的情况
        if (!stack.isEmpty())
            return false;
        // 检查'='号是否不在末尾
        if (!("=".equals(numStr.charAt(numStr.length() - 1) + "")))
            return false;
        return true;
    }
    /**
     * 判断字符是否是0-9的数字
     */
    private boolean isNumber(char num) {
        if (num >= '0' && num <= '9')
            return true;
        return false;
    }
    /**
     * 比较优先级：如果当前运算符比栈顶元素运算符优先级高则返回true，否则返回false
     */
    private boolean comparePri(char symbol) {
        if (symbolStack.empty()) { // 空栈返回true
            return true;
        }
        // 符号优先级说明（从高到低）:
        // 第1级: (
        // 第2级: + -
        // 第3级: *
        // 第4级: )
        char top = symbolStack.peek(); // 查看堆栈顶部的对象，注意不是出栈
        if (top == '(') {
            return true;
        }
        // 比较优先级
        switch (symbol) {
            case '(': // 优先级最高
                return true;
            case '+': {
                // 优先级比*高
                return top == '*';
            }
            case '-': {
                // 优先级比*高
                return top == '*';
            }
            case '*':
                return false;
            case ')': // 优先级最低
                return false;
            case '=': // 结束符
                return false;
            default:
                break;
        }
        return true;
    }
}

只通过了80%，没有判断数字间空格以及负数

第一题蹭了33%，第三题6%。