C8. C语言模拟入栈

记录一下，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. 遇到加减法直接入栈，加法入栈正数，减法入栈负数。

源码：在社区中找到了一篇比较优秀的代码，这里直接贴上作者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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/