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 文章来源地址https://www.toymoban.com/news/detail-729354.html

到了这里,关于Java算法题 给一个字符串表达式,实现一个基本计算器,返回计算结果的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 从零开始学Java56--与字符串相关的正则表达式

    在上一篇文章中给大家介绍了 String字符串及其各种常用API方法 ,接下来继续给大家讲解一些 String字符串的高级玩法。 有时候我们操作一个字符串时,这个字符串的内容并不一定就是固定不变的。比如在用户注册时,我们要求用户在输入框中输入自己的手机号码。我们知道,

    2024年02月06日
    浏览(43)
  • 56从零开始学Java之与字符串相关的正则表达式

    作者 :孙玉昌,昵称【 一一哥 】,另外【 壹壹哥 】也是我哦 CSDN博客专家、万粉博主、阿里云专家博主、掘金优质作者 在上一篇文章中, 壹哥 给大家介绍了String字符串及其各种常用API方法,接下来 壹哥 继续给大家讲解一些String字符串的高级玩法。 有时候我们操作一个字

    2024年02月14日
    浏览(42)
  • 【编译原理】【词法分析】【正则表达式】【NFA】【DFA】【C++】正则表达式转DFA&NFA,判断字符串是否符合正则表达式的匹配算法

    显然,正则表达式、NFA、DFA的概念都很简单,所以直接上代码,注释应该解释地比较清楚, 没有万能头文件的自行替换需求库 ,如果有疑问的可以留言。 网盘链接 [自行补全]/s/1pbGT_wpB662TwFrnukXgGQ?pwd=TSIT 提取码:TSIT 原理可以参考这篇博客 传送门 本次程序由四个文件组成 文

    2024年02月11日
    浏览(87)
  • 华为OD机试 - 数字字符串组合倒序 - 正则表达式(Java 2023 B卷 100分)

    华为OD机试 2023B卷题库疯狂收录中,刷题

    2024年02月09日
    浏览(48)
  • 算法训练day11Leetcode20有效的括号1047删除字符串中所有相邻重复项150逆波兰表达式求值

    https://leetcode.cn/problems/valid-parentheses/description/ https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html 判断右括号后忘记pop 括号匹配是使用栈解决的经典问题。 如果还记得编译原理的话,编译器在 词法分析的过程中处理括号、花括号等这个符号的逻辑,也是使用了栈

    2024年01月17日
    浏览(75)
  • 华为OD机试 - 提取字符串中的最长合法简单数学表达式(Java & JS & Python & C)

    题目描述 提取字符串中的最长合法简单数学表达式,字符串长度最长的,并计算表达式的值。如果没有,则返回 0 。 简单数学表达式只能包含以下内容: 0-9数字,符号+-* 说明: 所有数字,计算结果都不超过long 如果有多个长度一样的,请返回第一个表达式的结果 数学表达

    2024年02月02日
    浏览(50)
  • 12.字符串和正则表达式

    正则表达式相关知识 在编写处理字符串的程序或网页时,经常会有查找符合某些复杂规则的字符串的需要,正则表达式就是用于描述这些规则的工具,换句话说正则表达式是一种工具,它定义了字符串的匹配模式(如何检查一个字符串是否有跟某种模式匹配的部分或者从一个

    2024年01月16日
    浏览(61)
  • 提取字符串中的最长数学表达式并计算(67%用例) C卷(Java&&Python&&C++&&Node.js&&C语言)

    提取字符串中的最长合法简单数学表达式,字符串长度最长的,并计算表达式的值。如果没有,则返回0 简单数学表达式只能包含以下内容 0-9数字,符号+-* 说明: 1.所有数字,计算结果都不超过long 2.如果有多个长度一样的,请返回第一个表达式的结果 3.数学表达式,必须是最

    2024年04月13日
    浏览(38)
  • .NET实现解析字符串表达式

    我们创建了一个 School 对象,其中包含了教师列表和学生列表。现在,我们需要计算教师平均年龄和学生平均年龄。 如果我们将计算教师平均年龄的公式交给用户定义,那么用户可能会定义一个字符串来表示: Teachers.Sum(Age)/Teachers.Count 或者可以通过lambda来表示: teachers.Averag

    2023年04月21日
    浏览(37)
  • python 正则表达式提取字符串

    1、提取字符串的场景及公式、命令 背景 :目前遇到的场景主要是以某个字符串开始、某个字符串结束,提取中间部分的字符,有的时候需要开始的字符,有时不需要,大概涉及到了4种情况,场景及处理方式如下: 1.1 以某个字符开始、某个字符结束,期待的提取结果 包含

    2024年02月02日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包