1.3.45

1.3.45 #

解答 #

书上已经给出了思路，简单说明一下。

第一问是给定输入判断是否会下溢出，只要记录栈中元素的数量即可，一旦为负数则返回 true。

第二问是给定输出判断是否可能。

对于输出序列中的每一个数，如果栈顶为空或者栈顶数字小于当前输出序列的数，那么就从输入序列中输入数字，直到栈顶数字和当前输出序列中的数字相等。

如果当前输出序列中的数字和栈顶元素相等，从栈中弹出相应元素。

最后如果栈为空则可能，否则不可能。

可以结合习题 1.3.3 的解答查看。

通用解法见下一题。

代码 #

// 给定输入序列，判断是否会出现下溢出。
var input = "- 0 1 2 3 4 5 6 7 8 9 - - - - - - - - -";
Console.WriteLine(IsUnderflow(input.Split(' '))); //True
input = "0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 -";
Console.WriteLine(IsUnderflow(input.Split(' '))); //False

// 给定输出序列，判定是否可能。
int[] output = { 4, 3, 2, 1, 0, 9, 8, 7, 6, 5 };
Console.WriteLine(IsOutputPossible(output)); //True
output = new[] { 4, 6, 8, 7, 5, 3, 2, 9, 0, 1 };
Console.WriteLine(IsOutputPossible(output)); //False

static bool IsUnderflow(string[] input)
{
    // 记录栈中元素数量，如果元素数量小于 0 则会出现下溢出。
    var count = 0;

    foreach (var s in input)
    {
        if (count < 0)
        {
            return true;
        }

        if (s.Equals("-"))
        {
            count--;
        }
        else
        {
            count++;
        }
    }

    return false;
}

static bool IsOutputPossible(int[] output)
{
    var input = 0;
    var n = output.Length;
    var stack = new Stack<int>();

    foreach (var i in output)
    {
        // 如果栈为空，则从输入序列中压入一个数。
        if (stack.IsEmpty())
        {
            stack.Push(input);
            input++;
        }

        // 如果输入序列中的所有数都已经入栈过了，跳出循环。
        if (input == n && stack.Peek() != i)
        {
            break;
        }

        // 如果输出序列的下一个数不等于栈顶的数，那么就从输入序列中压入一个数。
        while (stack.Peek() != i && input < n)
        {
            stack.Push(input);
            input++;
        }

        // 如果栈顶的数等于输出的数，弹出它。
        if (stack.Peek() == i)
        {
            stack.Pop();
        }
    }

    return stack.IsEmpty();
}

另请参阅 #

Generics 库