Java算法题 给一个字符串表达式，实现一个基本计算器，返回计算结果_java计算字符串表达式

题目：

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

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

        输出描述：
        计算出结果值

        示例1
        输入：
        400+5
        复制
        输出：
        405

考点：栈

解题思路：

使用 2 个栈，一个 stack_nums 用来保存计算过程的操作数，一个 stack_symbol 用来保存运算符。

在HashMap中，指定加减优先级为1，乘除优先级为2

循环遍历字符串s，

1. 操作符入栈：

   若当前字符为'+', '-', '*', '/', '(' 时，压入运算符栈 stack_symbol，

2. 操作数入栈：

   若当前字符为数值类型，相当于循环读取字符串转化为十进制整数，直到下一个字符为非数值类型，把它压入操作数栈中。

3. 执行运算：

   当遍历到加减乘除运算符时，判断栈stack_symbol内存在优先级大于等于当前运算符，则可以先执行一次运算，尽可能先消费栈stack_symbol内的运算符；

   当右括号出现时需要执行一次优先级运算，并从操作符栈内弹出对应的左括号；

4. 运算规则：栈是后进先出，参与加减乘除运算时，第一个从 stack_nums 栈顶弹出的数应在运算符后面，第二个 stack_nums 从栈顶弹出的数应在运算符前面。

1. 特殊情况处理：

• 括号的处理：

括号有2种情况，

第一种是负数携带的括号，即除了第一个位置出现的数外，后面的数为负数时所附带的括号，

第二种是，需要优先进行运算的式子

• 负数的处理：

对于负数的处理，增加一步 0 - n 运算，假设负号后面的数等于 n

开头第一个数带 '-' 号，s.charAt(0) == '-'

s = "0" + s;

或者括号 () 里面第一个数带 '-' 号，

s = s.replace( "(-", "(0-" );

认为是负号，否则认为是减号

当循环结束时，若栈stack_symbol内还有运算符，继续算完

import java.util.Scanner;
import java.util.Stack;
import java.util.Map;
import java.util.HashMap;
 
// 注意类名必须为 Main, 不要有任何 package xxx 信息
/**
 * @ClassName
 * @Description
 * @Author liulvhua
 * @Date 2023/4/5
 **/
public class HJ54 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Stack<Integer> stack_nums = new Stack<>();
        Stack<Character> stack_symbol = new Stack<>();
        Map<Character, Integer> map = new HashMap<>();
        map.put('+', 1);
        map.put('-', 1);
        map.put('*', 2);
        map.put('/', 2);
        while (sc.hasNextLine()) {
            String s = sc.nextLine();
            if (s.charAt(0) == '-') {//第一个数为负数
                s = "0" + s;
            }
            s = s.replace("(-", "(0-");//其他位置负数处理
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                if (ch == ' ') continue;
                if (ch == '(') {
                    stack_symbol.push(ch);
                    continue;
                }
                if (ch == ')') {
                    //括号结束计算一次
                    stack_nums.push(calculate(stack_nums, stack_symbol));
                    if (!stack_symbol.isEmpty() && stack_symbol.peek() == '(') {
                        //当前计算是括号内最后一次运算，弹出左括号
                        stack_symbol.pop();
                    }
                    continue;
                }
                if (map.containsKey(ch)) {
                    // 栈内至少有1个运算符且栈顶不是左括号，并且栈内运算符优先级大于等于当前运算符号优先级，执行一次计算，
                    // 即先消费已入栈的高优先级运算符
                    while (!stack_symbol.isEmpty() && stack_symbol.peek() != '(' && map.get(stack_symbol.peek()) >= map.get(ch)) {
                        stack_nums.push(calculate(stack_nums, stack_symbol));
                    }
                    stack_symbol.push(ch);
                } else {
                    int num = 0;
                    int j = i;//循环读取十进制整数
                    while (j < s.length() && Character.isDigit(s.charAt(j))) {
                        num = num * 10 + s.charAt(j) - '0';
                        j++;
                    }
                    stack_nums.push(num);
                    i = j - 1;
                }
            }
            // 循环结束还有未算尽的式子，优先级低
            while (!stack_symbol.isEmpty()) {
                stack_nums.push(calculate(stack_nums, stack_symbol));
                if (!stack_symbol.isEmpty() && stack_symbol.peek() == '(') {
                    stack_symbol.pop();
                }
            }
            System.out.println(stack_nums.pop());
        }
    }
 
    /**
     * 执行运算
     * @param stack_nums 操作数栈
     * @param stack_symbol 运算符栈
     * @return
     */
    public static int calculate(Stack<Integer> stack_nums, Stack<Character> stack_symbol) {
        int res = 0;
        int opt_nums2 = stack_nums.pop();
        int opt_nums1 = stack_nums.pop();
        char symbol = stack_symbol.pop();
        switch (symbol) {
            case '+': {
                res = opt_nums1 + opt_nums2;
                break;
            }
            case '-': {
                res = opt_nums1 - opt_nums2;
                break;
            }
            case '*': {
                res = opt_nums1 * opt_nums2;
                break;
            }
            case '/': {
                res = opt_nums1 / opt_nums2;
                break;
            }
        }
        return res;
    }
}

执行用例：

2*3-2*(1-2*2)-0
12
2*3-2*(1-2*(1-3))-0
-4
2*3-2*(1-2*(1-3))-0
-4
2*3-2*(1-2*(1-3)*(-1))-0
12