首页 > 编程语言 >(算法)基本计算器II————<栈—模拟>

(算法)基本计算器II————<栈—模拟>

时间:2024-08-29 21:24:22浏览次数:15  
标签:char int 可以 计算器 个数 II 算法 栈中

1. 题⽬链接:227.基本计算器II

2. 题⽬描述:

题⽬解析:

⼀定要认真看题⽬的提⽰,从提⽰中我们可以看到这道题:

• 只有「加减乘除」四个运算;

• 没有括号;

• 并且每⼀个数都是⼤于等于0 的;

这样可以⼤⼤的「减少」我们需要处理的情况。 

3. 解法(栈):

算法思路:

由于表达式⾥⾯没有括号,因此我们只⽤处理「加减乘除」混合运算即可。根据四则运算的顺序,我 们可以先计算乘除法,然后再计算加减法。由此,我们可以得出下⾯的结论:

• 当⼀个数前⾯是'+' 号的时候,这⼀个数是否会被⽴即计算是「不确定」的,因此我们可以先压 ⼊栈中;

• 当⼀个数前⾯是'-' 号的时候,这⼀个数是否被⽴即计算也是「不确定」的,但是这个数已经 和前⾯的-号绑定了,因此我们可以将这个数的相反数压⼊栈中;

• 当⼀个数前⾯是'*' 号的时候,这⼀个数可以⽴即与前⾯的⼀个数相乘,此时我们让将栈顶的元 素乘上这个数;

• 当⼀个数前⾯是'/' 号的时候,这⼀个数也是可以⽴即被计算的,因此我们让栈顶元素除以这个 数。 当遍历完全部的表达式的时候,栈中剩余的「元素之和」就是最终结果。  

C++算法代码: 

class Solution 
{
public:
    int calculate(string s) 
    {
        vector<int>answer;  //存储栈
        char key='+';   //记录数字前的运算符
        for(int i=0;i<s.size();)
        {
            //空格
            if(s[i]==' ')
            {
                i++;
            }
            //运算符
            if(!isdigit(s[i]))
            {
                key=s[i];
            }
            //数字字符
            else
            {
                int temp=0; //读取数字
                while(isdigit(s[i]))
                {
                    temp*=10;
                    temp+=s[i]-'0';
                    i++;
                }
                if(key=='*')
                {
                    answer.back()*=temp;
                }
                else if(key=='/')
                {
                    answer.back()/=temp;
                }
                else if(key=='-')
                {
                    answer.push_back(-temp);
                }
                else
                {
                    answer.push_back(temp);
                }
                continue;
            }
            i++;
        }
        //求和
        int sum=0;
        for(int i=0;i<answer.size();i++)
        {
            sum+=answer[i];
        }
        return sum;
    }
};

Java算法代码:

class Solution
{
	public int calculate(String _s)
	{
		Deque<Integer> st = new ArrayDeque<>();
		char op = '+';
		int i = 0, n = _s.length();
		char[] s = _s.toCharArray();
		while (i < n)
		{
			if (s[i] == ' ') i++;
			else if (s[i] >= '0' && s[i] <= '9')
			{
				int tmp = 0;
				while (i < n && s[i] >= '0' && s[i] <= '9')
				{
					tmp = tmp * 10 + (s[i] - '0');
					i++;
				}
				if (op == '+') st.push(tmp);
				else if (op == '-') st.push(-tmp);
				else if (op == '*') st.push(st.pop() * tmp);
				else st.push(st.pop() / tmp);
			}
			else
			{
				op = s[i];
				i++;
			}
		}
		// 统计结果 
		int ret = 0;
		while (!st.isEmpty())
		{
			ret += st.pop();
		}
		return ret;
	}
}

标签:char,int,可以,计算器,个数,II,算法,栈中
From: https://blog.csdn.net/2301_79580018/article/details/141688883

相关文章

  • (算法)⽐较含退格的字符串————<栈—模拟>
    1.题⽬链接:844.⽐较含退格的字符串2.题⽬描述:3.解法(⽤数组模拟栈):算法思路:由于退格的时候需要知道「前⾯元素」的信息,⽽且退格也符合「后进先出」的特性。因此我们可以使⽤「栈」结构来模拟退格的过程。•当遇到⾮#字符的时候,直接进栈;•当遇到#的时候,栈顶元素......
  • 数据结构与算法 第3天(栈和队列)
    栈和队列也是线性表,限制插入和删除的位置只能在端点栈(stack)后进先出LIFO表尾进入,表尾删除一、案例案例一:进制转换例子159转换成八进制159/8=19...719/8=2...32/8=0...2结果为237案例二:括号匹配的检验左括号先入栈,右括号有匹配的话与左括号一起出栈案例三:表......
  • python实现RC4加解密算法
    目录RC4算法简介RC4算法的加密和解密流程RC4算法的Python实现代码解释RC4算法的应用场景RC4的安全性分析总结RC4(RivestCipher4)是一种流加密算法,由RonRivest于1987年设计。RC4广泛应用于各种加密协议,如SSL/TLS和WEP/WPA等。RC4算法因其简单、高效的特点受到广泛关......
  • Python实现SM4加解密算法
    目录SM4算法简介SM4算法的加密和解密流程SM4算法的Python实现代码解释总结SM4算法是中国国家密码局设计的块密码算法,广泛应用于无线局域网标准和其他安全通信系统中。以下是SM4算法的详细介绍,包括加密解密流程和Python的完整实现。SM4算法简介SM4是一种对称分组......
  • Python实现等距映射(ISOMAP)降维算法
    目录Python实现等距映射(ISOMAP)降维算法的博客引言ISOMAP算法原理ISOMAP的优势与局限Python实现ISOMAP算法1.创建ISOMAP类2.在瑞士卷数据集上应用ISOMAP3.结果分析总结运行结果Python实现等距映射(ISOMAP)降维算法的博客引言在高维数据处理中,降维是一种常用的技......
  • 代码随想录算法训练营,29日 | 704. 二分查找,27. 移除元素,977.有序数组的平方,209.长度最
    数组基础文档讲解︰代码随想录(programmercarl.com)1.连续空间、相同类型元素2.元素只能覆盖3.二维数组的地址连续吗(C++连续,Java不连续)704.二分查找题目链接:704.二分查找文档讲解︰代码随想录(programmercarl.com)视频讲解︰二分查找日期:2024-08-29思路:第一反应是想到二分查......
  • .net Core发布IIS的各种异常解答
    一.IIS启动之后发布项目失败原因以及解决方案1.查看本机应用池模块是否有AspNetCoreMoudleV2,如果没有,需要去微软官网下载一个HostingBundle安装2.查看程序池的.netCLR版本要选择无托管代码3.标识应该选择localsystem二.打开网页提示用户登录数据失败原因以及解决方案1.......
  • Java算法之Gnome 排序
    简介Gnome排序,又称为双向插入排序或鸡尾酒排序,是一种改进的插入排序算法。它在每次迭代中不仅将最小的元素移动到前面,同时也将最大的元素移动到后面。这种排序算法在每次迭代中同时向两个方向进行移动,因此得名。算法步骤从数组的两端开始,向中间进行扫描。如果左侧元素大于......
  • Java算法之基数排序(Radix Sort)
    简介基数排序是一种非比较型整数排序算法,其原理是按照低位先排序,然后收集,再按照高位排序,再收集,依次类推,直到最高位。这种方法可以视为对每个位上的数字进行稳定的排序。算法步骤确定最大数的位数。对每一位进行排序:从最低位开始,使用稳定的排序算法(如计数排序)对当前位进......
  • 30-物体检测算法R-CNN SSD YOLO
    1、R-CNN2、FastR-CNN3、FasterR-CNN4、MaskR-CNN5、SSD6、YOLO......