LeetCode-困难-224-基本计算器-栈(C)

LeetCode题解目

题目

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

示例 1：

输入：s = "1 + 1"
输出：2
示例 2：

输入：s = " 2-1 + 2 "
输出：3
示例 3：

输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23
 

提示：

1 <= s.length <= 3 * 105
s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
s 表示一个有效的表达式

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

思路

• 有一说一，我用计算器的时候不打空格。
  • 不过至少这里的空格不会出现在数的中间。
• 用栈来解决：
  • 栈：
    • long* ele，保存元素值，用int处理比较麻烦，而且题目没说不能long。
    • int* type，保存类型，0表示括号，1表示正号，-1表示符号，2表示数。
    • ele与type是对应的。
    • top为栈顶，size为栈大小。
  • pos从左到右遍历s：
    • 每次遍历都判断一下这个值前面是否有一个完整的数，如果有，就入栈。
    • 再判断s[pos]的值：
      • 对于左括号、正号、符号的操作都是入栈，
      • 对于数字，将这个数转换成int型，
      • 对于右括号，就开始回退栈，将这对括号内部的值算出来，代替左括号的位置。
    • 这样，每次遍历时，栈中不会出现右括号。
      • 即每次出现右括号的时候，对应左括号都会消去，
      • 遍历完s，所有的右括号都出现，所有的左括号也对应消去，
      • 栈内将只剩下数与正负号。
  • 结束遍历后，再如同处理右括号一样，对栈内的元素求和。

代码

typedef struct stack{
    //type中，0表示括号，1表示正号，-1表示符号，2表示数。
    //如果type==2，则对应的ele存储其数
    //top为栈顶，size为栈大小。
    long* ele;
    int* type;
    int top;
    int size;
}stack;

int calculate(char * s){
    stack st;
    long temp;
    int pos, pos2;
    st.top = -1;
    st.size = 10;
    st.ele = malloc(sizeof(long) * st.size);
    st.type = malloc(sizeof(int) * st.size);
    for(pos = 0, temp = 0;    s[pos] != '\0'; pos++){
        if((s[pos] < '0' || s[pos] > '9') && pos != 0 && s[pos-1] >= '0' && s[pos-1] <= '9'){
            //前面是数，但该位置不是，将前面的数入栈
            pushStack(&st, 2, temp);
            temp = 0;
        }
        switch (s[pos]){
            case '(':
                pushStack(&st, 0, 0);
                break;
            case ' ':
                break;
            case '+':
                pushStack(&st, 1, 999);
                break;
            case '-':
                pushStack(&st, -1, -999);
                break;
            case ')':
                //出现右括号时，先入栈一个括号，用于表示这对括号的范围，再将括号内的数计算出来，替换这对括号中左括号的位置。
                pushStack(&st, 0, 0);
                for(st.top--;   st.type[st.top] != 0; st.top--); //找到前一个左括号
                st.top--;   //栈顶移动到左括号前
                pos2 = st.top + 2; //pos2定位到栈顶后的括号后。
                if(st.type[pos2] == 2) temp = st.ele[pos2]; //括号中第一个元素值，
                else temp = st.type[pos2] * st.ele[pos2 + 1];
                if(st.type[pos2 + 1] == 0) pos2--;  //如果这个括号只有一个数，pos2回退1，避免后续代码对其处理出错
                for(pos2 += 2;   st.type[pos2] != 0;  pos2++){  //累加括号中其他元素值
                    if(st.type[pos2] != 2) pos2++;
                    temp += st.type[pos2-1] * st.ele[pos2];
                }
                pushStack(&st, 2, temp);    //括号内的和，推入栈中。
                temp = 0;
                break;
            default:
                temp = temp * 10 + s[pos] - '0';
        }
    }
    pos--;
    if(s[pos] >= '0' && s[pos] <= '9'){ //s的最后位置是数字，则该数字所在的数，不在栈中，要入栈
        pushStack(&st, 2, temp);
    }
    //同上面对右括号的处理，这里是将栈内的数求和。
    if(st.type[0] == 2) temp = st.ele[0];
    else temp = st.type[0] * st.ele[1];
    for(pos = 2;    pos <= st.top;   pos++){
        if(st.type[pos] != 2) pos++;
        temp += st.type[pos-1] * st.ele[pos];
    }
    return temp;
}

void pushStack(stack* st, int t, long e){
    if(st->top / (st->size - 2) > 0){   //栈大小不足时扩充栈。
        st->size *= 10;
        st->ele = realloc(st->ele, st->size * sizeof(long));
        st->type = realloc(st->type, st->size * sizeof(int));
    }
    st->top += 1;
    st->type[st->top] = t;
    st->ele[st->top] = e;
}