Java题解 | HJ50 #四则运算#

四则运算

https://www.nowcoder.com/practice/9999764a61484d819056f807d2a91f1e

描述

输入一个表达式（用字符串表示），求这个表达式的值。

保证字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’， ‘)’,‘[’, ‘]’,‘{’ ,‘}’。且表达式一定合法。

数据范围：表达式计算结果和过程中满足 ∣val∣≤1000 ，字符串长度满足 1≤n≤1000

输入描述：

输入一个算术表达式

输出描述：

得到计算结果

示例

输入：

3+2*{1+2*[-4/(8-6)+7]}

输出：

解法

算术表达式一般是采用栈的结构。而本题是四则运算，则可采用双栈的结构。

什么是四则运算？

四则运算是指加法、减法、乘法和除法四种运算。四则运算是小学数学的重要内容。

如果加減乘除放在同一個算式列中的話，其計算的順序是“先乘除，後加減”，括號内先算。有多重括号的，先算小括號，再算中括號，最後算大括號。

例如，计算如下表达式1+2*3-8/4，该表达式为字符串的话，可以使用两个栈，一个栈存数字，一个栈存运算符，每次都是一个数字、一个运算符这样一对的进行比较和入栈。

具体计算步骤如下所示：

1. 将1和+分别入栈：

2. 将2和*分别入栈前，比较运算符的优先级，发现栈顶的运算符优先级小于将要进入的运算符，则不进行运算，将2和*入栈。

3. 将3和-分别入栈前，比较运算符的优先级，发现栈顶的运算符优先级高于将要进入的运算符，则将3、2以及*做四则运算得出6，将2和*出栈，将6和-入栈。

4. 将8和/分别入栈，比较运算符的优先级，发现栈顶的运算符优先级小于将要进入的运算符，则不进行运算，将8和/入栈。

5. 将最后一个数字和栈中的所有数字和运算符进行计算，直到运算符栈为空。

解题步骤

初始化两个栈operatorStack、numberStack，分别用于存放运算符和数字。
接收这一整串的字符串，并从第一个字符开始，遍历字符串。
不管是大、中、小括号，处理方式一样，遇到左括号，忽略。
遇到数字，存入数字栈；遇到运算符，存入运算符栈。
不管是大、中、小括号，处理方式一样，，遇到右括号，开始计算，取出数字栈最顶上两个元素，以及运算符栈最顶上一个元素，用数字栈倒数第二个元素通过运算符和第一个元素进行运算。
将计算的结果再压入数字栈。
重复2-5，直到遇到最后一个括号，则计算结束，返回最终数字栈中的唯一元素。

/*
 * Copyright (c) waylau.com, 2022. All rights reserved.
 */

package com.waylau.nowcoder.exam.oj.huawei;

import java.util.Scanner;
import java.util.Stack;

/**
 * 描述：输入一个表达式（用字符串表示），求这个表达式的值。 保证字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’，
 * ‘)’,‘[’, ‘]’,‘{’ ,‘}’。 且表达式一定合法。 数据范围：表达式计算结果和过程中满足 ∣val∣≤1000 ，字符串长度满足
 * 1≤n≤1000 输入描述：输入一个算术表达式 输出描述： 得到计算结果 示例 输入： 3+2*{1+2*[-4/(8-6)+7]} 输出： 25
 *
 * @author <a href="https://waylau.com">Way Lau</a>
 * @since 2022-08-24
 */
public class HJ050FourArithmeticOperations {     public static void main(String[] args) {         // 输入         Scanner in = new Scanner(System.in);         String str = in.nextLine();         // 中括号、大括号全部转为小括号，方便处理         str = str.replace('[', '(');         str = str.replace('{', '(');         str = str.replace(']', ')');         str = str.replace('}', ')');                  // 为了统一计算逻辑，在最外面的表达式也放括号         if (str.charAt(0) != '(') {             str = '(' + str + ')';         }         // 输出         System.out.println(solve(str));         // 关闭         in.close();     }     private static int solve(String str) {         char[] charArray = str.toCharArray();         int length = charArray.length;         // 用于存放数字。         Stack<Integer> stack = new Stack<>();         // 纪录数字         int number = 0;         // 纪录上个操作符         char opr = '+';         for (int i = 0; i < length; i++) {             char ch = charArray[i];             // 一直入栈             // 遇到右括号就出栈，直到左括号出现为止             // 括号内包裹的表达式进行计算             // 如果当前字符是小括号             if (ch == '(') {                 // 移到小括号后一位字符                 int j = i + 1;                 // 统计括号的数量                 int count = 1;                 while (count > 0) {                     // 遇到右括号，括号数-1                     if (charArray[j] == ')') {                         count--;                     }                     // 遇到左括号，括号数+1                     if (charArray[j] == '(') {                         count++;                     }                     j++;                 }                 // 递归，解小括号中的表达式                 number = solve(str.substring(i + 1, j - 1));                 i = j - 1;             } else if (Character.isDigit(ch)) {                 // 多为数字的处理，ch-'0'是转为整数                 number = number * 10 + ch - '0';             }             if (!Character.isDigit(ch) || i == length - 1) {                 // 遇到符号，将数字处理后放进栈                 // 如果是'+',直接入栈                 if (opr == '+') {                     stack.push(number);                 }                 // 如果是'-',数字取相反数在入栈                 else if (opr == '-') {                     stack.push(-1 * number);                 }                 // 如果是'*',弹出一个数字乘后放入栈                 else if (opr == '*') {                     stack.push(stack.pop() * number);                 }                 // 如果是'/',弹出一个数字/后放入栈                 else if (opr == '/') {                     stack.push(stack.pop() / number);                 }                 // 更新符号                 opr = ch;                 // 刷新数字                 number = 0;             }         }         // 栈中数字求和得到结果         int sum = 0;         while (!stack.isEmpty()) {             sum += stack.pop();         }         return sum;     }

}