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;
}

You may also like...

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注