首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >模拟入栈操作

模拟入栈操作

作者头像
开源519
发布2020-09-22 10:01:13
4040
发布2020-09-22 10:01:13
举报
文章被收录于专栏:开源519开源519

记录一下,C语言中一道比较经典的题目 -- 模拟入栈:

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式仅包含非负整数,+, - ,*,/ 四种运算符和空格 。 整数除法仅保留整数部分。

示例 1:

输入: "3+2*2"
输出: 7
示例 2:

输入: " 3/2 "
输出: 1
示例 3:

输入: " 3+5 / 2 "
输出: 5
说明:

你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/basic-calculator-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

  • 注意的问题:
  1. 注意屏蔽输入中的空格。
  2. 乘法与除法运算优先级高于加减法。
  • 解决思路
  1. 新建一个数组模拟栈,将输入的有效字符转成整型入栈。
  2. 在入栈过程中遇到乘除直接与栈顶数据运算,并将结果更新到栈顶数据。
  3. 遇到加减法直接入栈,加法入栈正数,减法入栈负数。
  4. 最后将数组中的值求和。

源码(在社区中找到了一篇比较优秀的代码,这里直接贴上作者stailor的源码):

// 得到如果出现超过两位以上的数
long cal(char * s, int* pos) {
    long temp = 0;
    while (s[*pos] >= '0' && s[*pos] <= '9') {
        temp = temp * 10 + s[*pos] - '0';
        (*pos)++;
    }
    (*pos)--;
    return temp;
}

int calculate(char * s){
    int pos = 0;
    int len = strlen(s);
    long* stack = (long*)calloc(len, sizeof(long));
    int top = -1;
    int flag = 1;
    while (s[pos] != '\0') {
        // 删除空格
        while (s[pos] == ' ') {
            pos++;
        }
        // 根据前个符号,加减则栈顶加1,乘除则与栈顶相计算更新栈顶元素
        if (s[pos] >= '0' && s[pos] <= '9') {
            if (flag == 1) {
                stack[++top] = cal(s, &pos);
            } else if (flag == 2) {
                stack[++top] = -cal(s, &pos);
            } else if (flag == 3) {
                stack[top] = stack[top] * cal(s, &pos);
            } else if (flag == 4) {
                stack[top] = stack[top] / cal(s, &pos);
            }
        }
        // 根据符号设置FLAG
        if (s[pos] == '+') {
            flag = 1;
        } else if (s[pos] == '-') {
            flag = 2;
        } else if (s[pos] == '*') {
            flag = 3;
        } else if (s[pos] == '/') {
            flag = 4;
        }
        
        if (s[pos] == '\0') {
            break;
        }
        pos++;
    }
    int sum = 0;
    // sum栈内元素
    for (int i = 0; i <= top; i++) {
        sum += stack[i];
    }

    return sum;
}

/*
作者:stailor
链接:https://leetcode-cn.com/problems/basic-calculator-ii/solution/yong-shu-zu-mo-ni-zhan-jin-xing-ji-suan-by-stailor/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
*/

这里附上栈的操作示意图:

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-09-14,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 开源519 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档