您的位置:首页 > 科技 > 能源 > 华为OD机考题(HJ50 四则运算)

华为OD机考题(HJ50 四则运算)

2024/12/23 16:04:58 来源:https://blog.csdn.net/acuteeagle01/article/details/140141524  浏览:    关键词:华为OD机考题(HJ50 四则运算)

前言

经过前期的数据结构和算法学习,开始以OD机考题作为练习题,继续加强下熟练程度。

描述

输入一个表达式(用字符串表示),求这个表达式的值。

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

数据范围:表达式计算结果和过程中满足 ∣𝑣𝑎𝑙∣≤1000 ∣val∣≤1000  ,字符串长度满足 1≤𝑛≤1000 1≤n≤1000 

输入描述:

输入一个算术表达式

输出描述:

得到计算结果

示例1

输入:

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

25

实现原理

在 Java 中实现支持负数、大括号、中括号和小括号的四则运算,可以通过以下步骤:

  1. 处理括号:将中缀表达式中的大括号 {}, 中括号 [] 和小括号 () 全部转换成统一的小括号 ()
  2. 中缀转后缀:将中缀表达式转换为后缀表达式(RPN)。
  3. 计算后缀表达式:使用栈计算后缀表达式的值。

实现代码

import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);String expression = in.nextLine();expression = replaceBrackets(expression);List<String> postfix = infixToPostfix(expression);int result = evaluatePostfix(postfix);System.out.println(result);}// 判断是否是运算符private static boolean isOperator(char c) {return c == '+' || c == '-' || c == '*' || c == '/';}// 获取运算符的优先级private static int precedence(char c) {switch (c) {case '+':case '-':return 1;case '*':case '/':return 2;default:return -1;}}// 将表达式中的大括号和中括号替换为小括号private static String replaceBrackets(String expression) {return expression.replace('{', '(').replace('}', ')').replace('[', '(').replace(']', ')');}// 将中缀表达式转换为后缀表达式public static List<String> infixToPostfix(String expression) {Stack<Character> stack = new Stack<>();List<String> postfix = new ArrayList<>();int n = expression.length();for (int i = 0; i < n; i++) {char c = expression.charAt(i);// 如果是数字或者负号开头的数字if (Character.isDigit(c) || (c == '-' && (i == 0 ||expression.charAt(i - 1) == '('))) {StringBuilder number = new StringBuilder();number.append(c);i++;while (i < n && Character.isDigit(expression.charAt(i))) {number.append(expression.charAt(i));i++;}i--;postfix.add(number.toString());}// 左括号else if (c == '(') {stack.push(c);}// 右括号else if (c == ')') {while (!stack.isEmpty() && stack.peek() != '(') {postfix.add(String.valueOf(stack.pop()));}stack.pop();}// 运算符else if (isOperator(c)) {while (!stack.isEmpty() && precedence(stack.peek()) >= precedence(c)) {postfix.add(String.valueOf(stack.pop()));}stack.push(c);}}// 将栈中剩余的运算符添加到后缀表达式while (!stack.isEmpty()) {postfix.add(String.valueOf(stack.pop()));}return postfix;}// 计算逆波兰表达式的值public static int evaluatePostfix(List<String> postfix) {Stack<Integer> stack = new Stack<>();for (String token : postfix) {if (isOperator(token.charAt(0)) && token.length() == 1) {int b = stack.pop();int a = stack.pop();switch (token.charAt(0)) {case '+':stack.push(a + b);break;case '-':stack.push(a - b);break;case '*':stack.push(a * b);break;case '/':if (b == 0) {throw new ArithmeticException("除数不能为零");}stack.push(a / b);break;}} else {stack.push(Integer.parseInt(token));}}return stack.pop();}
}

函数说明:

  • isOperator 方法

    • 判断一个字符是否是运算符(+、-、*、/)。
  • precedence 方法

    • 获取运算符的优先级,* 和 / 的优先级高于 + 和 -。
  • replaceBrackets 方法

    • 将表达式中的大括号 {} 和中括号 [] 替换为小括号 ()
  • infixToPostfix 方法

    • 将中缀表达式转换为后缀表达式。使用栈处理运算符和括号,处理过程中需要特别注意负数的情况。
  • evaluatePostfix 方法

    • 使用栈计算后缀表达式的值。遍历后缀表达式的每个 token,如果是运算符,则从栈中弹出两个操作数进行计算,并将结果压入栈中;如果是数字,则直接压入栈中。

1.QA:

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com