栈的压入、弹出序列

1.问题描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

1. 0<=pushV.length == popV.length <=1000
2. -1000<=pushV[i]<=1000
3. pushV 的所有数字均不相同

2.源码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const char *getArray(const char *buf, int *arr, int *n)
{
    const char *p = buf;
    char num[12];
    int i;

    while(*p != '[')
    {
        p++;
    }

    while(*n < 1001)
    {
        while(*p != '+' && *p != '-' && (*p < '0' || *p > '9'))
        {
            p++;
        }

        i = 0;

        if(*p == '+')
        {
            p++;
        }
        else if(*p == '-')
        {
            num[i] = '-';
            i++;
            p++;
        }

        if(*p < '0' || *p > '9')
        {
            return NULL;
        }

        while(*p >= '0' && *p <= '9' && i<11)
        {
            num[i] = *p;
            i++;
            p++;
        }

        while(*p != ']' && *p != 0x00 && *p != ' ' && *p != ',')
        {
            p++;
        }

        if(*p == ' ')
        {
            while(*p == ' ')
            {
                p++;
            }
        }

        if(*p == ']' || *p == ',')
        {
            num[i] = 0x00;

            arr[*n] = atoi(num);

            (*n)++;
        }

        i = 0;

        if(*p == ']' || *p == 0x00)
        {
            break;
        }
    }

    return p;
}

int main()
{
    char buf[512];
    int stack[3][1000];
    const char *p;
    int n = 0;
    int m = 0;
    int i;
    int j;
    int k;
    int w;

    memset(buf, 0x00, sizeof(buf));
    memset(stack, 0x00, sizeof(stack));

    fgets(buf, 511, stdin);

    p = getArray(buf, stack[0], &n);

    if(p == NULL)
    {
        return -1;
    }

    p = getArray(p+2, stack[1], &m);

    if(m != n)
    {
        return -1;
    }

    w = 0;

    for(i=0; i<n; i++)
    {
        while(1)
        {
            if(w && stack[2][w-1] == stack[1][i])
            {
                w--;
                break;
            }
            else
            {
                if(j < n)
                {
                    stack[2][w] = stack[0][j];
                    j++;
                    w++;
                }
                else
                {
                    break;
                }
            }
        }
    }

    if(w == 0)
    {
        printf("true\n");
    }
    else
    {
        printf("false\n");
    }

    return 0;
}

3.编译源码

$ gcc -o test test.c -std=c89

4.运行及其结果

$ ./test
[1,2,3,4,5],[4,5,3,2,1]
true