题目:
描述 给定一个字符串描述的算术表达式,计算出结果值。 输入字符串长度不超过 100 ,合法的字符包括 ”+, -, *, /, (, )” , ”0-9” 。 数据范围:运算过程中和最终结果均满足∣val∣≤2^31−1 ,即只进行整型运算,确保输入的表达式合法 输入描述: 输入算术表达式 输出描述: 计算出结果值 示例1 输入: 400+5 复制 输出: 405
考点:栈
解题思路:
使用 2 个栈,一个 stack_nums 用来保存计算过程的操作数,一个 stack_symbol 用来保存运算符。
在HashMap中,指定加减优先级为1,乘除优先级为2
循环遍历字符串s,
操作符入栈:
若当前字符为'+', '-', '*', '/', '(' 时,压入运算符栈 stack_symbol,
操作数入栈:
若当前字符为数值类型,相当于循环读取字符串转化为十进制整数,直到下一个字符为非数值类型,把它压入操作数栈中。
执行运算:
当遍历到加减乘除运算符时,判断栈stack_symbol内存在优先级大于等于当前运算符,则可以先执行一次运算,尽可能先消费栈stack_symbol内的运算符;
当右括号出现时需要执行一次优先级运算,并从操作符栈内弹出对应的左括号;
运算规则:栈是后进先出,参与加减乘除运算时,第一个从 stack_nums 栈顶弹出的数应在运算符后面,第二个 stack_nums 从栈顶弹出的数应在运算符前面。
特殊情况处理:
括号的处理:
括号有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;
}
}
执行用例:文章来源:https://www.toymoban.com/news/detail-729354.html
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 文章来源地址https://www.toymoban.com/news/detail-729354.html
到了这里,关于Java算法题 给一个字符串表达式,实现一个基本计算器,返回计算结果的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!