Leetcode 224 Basic Calculator 基本计算器

2024-01-13 11:48

本文主要是介绍Leetcode 224 Basic Calculator 基本计算器,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

原题地址

https://leetcode.com/problems/basic-calculator/

题目描述

Implement a basic calculator to evaluate a simple expression string.
实现基本的计算器,计算简单表达式的值。

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
表达式中可能会出现括号( ),加号+减号-,非负数以及空格。

You may assume that the given expression is always valid.
假设表达式都是正确的。

Some examples:
例如:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

解题思路

由于表达式中只有+ -两种运算符,因此不用考虑优先级的问题,唯一需要处理的是括号带来的计算顺序问题。考虑遍历整个字符串,当遇到( + -合法数字时,将相应字符或数字压栈,当遇到)时,从栈中弹出运算符及数字直到与这个括号匹配的开括号为止,并计算弹出的运算符和数字的结果,计算结束后压栈,然后继续遍历表达式。

在上述过程结束后,栈中还留有一些运算符合数字,但是不再包含括号,这时弹出所有运算符和数字进行一次运算即可得到最终结果。

代码

class Solution {
public:/** 简单表达式计算 */int calculate(string s) { stack<string> expr, nums, ops;int cur = 0, len = s.size();string tmp = "";while (cur < len) {// 获取下一个操作数或操作符switch (s[cur]) {case ' ': break;    // 忽略空格case '+':           // 如果遇到特殊字符case '-': case '(': if (tmp != "") {// 添加可能存在的操作数expr.push(tmp);tmp = "";}expr.push(tmp + s[cur]); // 添加特殊字符break;case ')': {         // 遇到闭合括号if (tmp != "") {// 添加可能存在的操作数expr.push(tmp);tmp = "";}               // 计算最顶层的括号内的子表达式int caled = calculate(expr);expr.push(intToStr(caled)); // 添加到栈中break;}default:    // 扩展操作数tmp += s[cur];break;}++cur;}if (tmp != "") expr.push(tmp);return calculate(expr); // 计算}
private:/** 计算栈中最上层的括号内的表达式 */int calculate(stack<string>& s) {stack<int> nums; stack<char> ops;string top;// 获取最顶层括号内的操作数和操作符while (!s.empty() && (top = s.top()) != "(") {if (top == "+" || top == "-")ops.push(top[0]);elsenums.push(strToInt(top));s.pop();}if (!s.empty()) s.pop(); // 弹出"("// 计算子表达式结果int ans = nums.top(), num;nums.pop();while (!ops.empty()) {num = nums.top();nums.pop();if (ops.top() == '+')ans += num;elseans -= num;ops.pop();}return ans;}int strToInt(string s) {int ans = 0, len = s.size();if (len == 0) return 0;int symbol = s[0] == '-' ? -1 : 1;for (int i = s[0] == '+' || s[0] == '-' ? 1 : 0; i < len; ++i) {ans *= 10;ans += s[i] - '0';}return ans * symbol;}string intToStr(int num) {if (num == 0) return "0";int symbol = num >= 0 ? 1 : -1;string s = "";num *= symbol;while (num) {s = (char)(num % 10 + '0') + s;num /= 10;}if (symbol == -1)s = "-" + s;return s;}
};

完整代码 https://github.com/Orange1991/leetcode/blob/master/224/cpp/main.cpp

测试数据

(1+(4+5+2 ) - 3) + (6+8)=23
1 + 1=22-1 + 2 =32-(5-6) =3

2015/8/28

这篇关于Leetcode 224 Basic Calculator 基本计算器的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/601352

相关文章

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

Go语言数据库编程GORM 的基本使用详解

《Go语言数据库编程GORM的基本使用详解》GORM是Go语言流行的ORM框架,封装database/sql,支持自动迁移、关联、事务等,提供CRUD、条件查询、钩子函数、日志等功能,简化数据库操作... 目录一、安装与初始化1. 安装 GORM 及数据库驱动2. 建立数据库连接二、定义模型结构体三、自动迁

ModelMapper基本使用和常见场景示例详解

《ModelMapper基本使用和常见场景示例详解》ModelMapper是Java对象映射库,支持自动映射、自定义规则、集合转换及高级配置(如匹配策略、转换器),可集成SpringBoot,减少样板... 目录1. 添加依赖2. 基本用法示例:简单对象映射3. 自定义映射规则4. 集合映射5. 高级配置匹

SQL BETWEEN 语句的基本用法详解

《SQLBETWEEN语句的基本用法详解》SQLBETWEEN语句是一个用于在SQL查询中指定查询条件的重要工具,它允许用户指定一个范围,用于筛选符合特定条件的记录,本文将详细介绍BETWEEN语... 目录概述BETWEEN 语句的基本用法BETWEEN 语句的示例示例 1:查询年龄在 20 到 30 岁

mysql中insert into的基本用法和一些示例

《mysql中insertinto的基本用法和一些示例》INSERTINTO用于向MySQL表插入新行,支持单行/多行及部分列插入,下面给大家介绍mysql中insertinto的基本用法和一些示例... 目录基本语法插入单行数据插入多行数据插入部分列的数据插入默认值注意事项在mysql中,INSERT I

mapstruct中的@Mapper注解的基本用法

《mapstruct中的@Mapper注解的基本用法》在MapStruct中,@Mapper注解是核心注解之一,用于标记一个接口或抽象类为MapStruct的映射器(Mapper),本文给大家介绍ma... 目录1. 基本用法2. 常用属性3. 高级用法4. 注意事项5. 总结6. 编译异常处理在MapSt

MyBatis ResultMap 的基本用法示例详解

《MyBatisResultMap的基本用法示例详解》在MyBatis中,resultMap用于定义数据库查询结果到Java对象属性的映射关系,本文给大家介绍MyBatisResultMap的基本... 目录MyBATis 中的 resultMap1. resultMap 的基本语法2. 简单的 resul

Java 枚举的基本使用方法及实际使用场景

《Java枚举的基本使用方法及实际使用场景》枚举是Java中一种特殊的类,用于定义一组固定的常量,枚举类型提供了更好的类型安全性和可读性,适用于需要定义一组有限且固定的值的场景,本文给大家介绍Jav... 目录一、什么是枚举?二、枚举的基本使用方法定义枚举三、实际使用场景代替常量状态机四、更多用法1.实现接

git stash命令基本用法详解

《gitstash命令基本用法详解》gitstash是Git中一个非常有用的命令,它可以临时保存当前工作区的修改,让你可以切换到其他分支或者处理其他任务,而不需要提交这些还未完成的修改,这篇文章主要... 目录一、基本用法1. 保存当前修改(包括暂存区和工作区的内容)2. 查看保存了哪些 stash3. 恢

基于Python开发一个有趣的工作时长计算器

《基于Python开发一个有趣的工作时长计算器》随着远程办公和弹性工作制的兴起,个人及团队对于工作时长的准确统计需求日益增长,本文将使用Python和PyQt5打造一个工作时长计算器,感兴趣的小伙伴可... 目录概述功能介绍界面展示php软件使用步骤说明代码详解1.窗口初始化与布局2.工作时长计算核心逻辑3