怎么做网站海外推广,视频网站dedecms,关键词优化排名公司,用仿站工具做网站前言
经过前期的数据结构和算法学习#xff0c;开始以OD机考题作为练习题#xff0c;继续加强下熟练程度。
描述
输入一个表达式#xff08;用字符串表示#xff09;#xff0c;求这个表达式的值。
保证字符串中的有效字符包括[‘0’-‘9’],‘’,‘-’, ‘*’,‘/’ …前言
经过前期的数据结构和算法学习开始以OD机考题作为练习题继续加强下熟练程度。
描述
输入一个表达式用字符串表示求这个表达式的值。
保证字符串中的有效字符包括[‘0’-‘9’],‘’,‘-’, ‘*’,‘/’ ,‘(’ ‘)’,‘[’, ‘]’,‘{’ ,‘}’。且表达式一定合法。
数据范围表达式计算结果和过程中满足 ∣∣≤1000 ∣val∣≤1000 字符串长度满足 1≤≤1000 1≤n≤1000
输入描述
输入一个算术表达式
输出描述
得到计算结果
示例1 输入 32*{12*[-4/(8-6)7]} 输出 25 实现原理
在 Java 中实现支持负数、大括号、中括号和小括号的四则运算可以通过以下步骤
处理括号将中缀表达式中的大括号 {}, 中括号 [] 和小括号 () 全部转换成统一的小括号 ()。中缀转后缀将中缀表达式转换为后缀表达式RPN。计算后缀表达式使用栈计算后缀表达式的值。
实现代码
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);ListString 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 ListString infixToPostfix(String expression) {StackCharacter stack new Stack();ListString 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(ListString postfix) {StackInteger 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:
