1.车厢调度

题目描述

    有一个火车站只有一个出入口，每辆火车从一边A驶入，再从另一个方向B驶出，同时它的车厢可以重新组合。假设从A方向驶来的火车有n节（n<=1000），分别按照顺序编号为1，2，3，…，n。假定在进入车站前，每节车厢之间都不是连着的，并且它们可以自行移动到B处的铁轨上。另外假定车站C可以停放任意多节车厢。但是一旦进入车站C，它就不能再回到A方向的铁轨上了，并且一旦当它进入B方向的铁轨，它就不能再回到车站C。

负责车厢调度的工作人员需要知道能否使它以a1,a2,…,an的顺序从B方向驶出，请来判断能否得到指定的车厢顺序。

输入

    输入的第一行为一个整数n，其中n<=1000，表示有n节车厢，第二行为n个数字，表示指定的车厢顺序。

输出

    如果可以得到指定的车厢顺序，则输出一个字符串”YES”，否则输出”NO”（注意要大写，不包含引号）。

样例输入：                 样例输出：

5                              YES

5 4 3 2 1

 

 

题目解析：

    显然该火车站是一个栈，所以该题是简单的栈的使用。因火车只能按编号1、2、3……到来，所以使用cnt记录当前已到达的最后的火车编号。因为是判断能否得到指定车厢顺序，所以对于给定顺序的每一个数，我们都得从前往后依次保证，即首先保证第一个出栈的是a1，然后第二个出栈的是a2……

    对于a1来说，想要使它第一个出栈唯一的方法就是先不断使编号比它低的火车进栈，即让1、2、3……a1-1进栈，随后a1进栈，然后立马出栈。否则如果在a1进栈前有火车出栈，或是a1进栈后还继续有火车进栈，则不可能a1先出栈。同理，若在第i轮时，此时已到达的最后的火车编号cnt若小于ai，则需要继续不断进栈直到cnt等于ai，然后出栈。我们可以发现，如果指定的车厢顺序不断按编号递增着来，则一定能满足要求的顺序。

    但若遍历至某个ai，而ai小于cnt时，则说明ai必然已经入栈了。此时若想要满足顺序，则必须下一个出栈的是ai。而因栈中能出栈的只有栈顶元素，所以必须栈顶元素得是ai才可以保证该顺序成立。而若栈顶元素不是ai，则必然无法满足该出栈顺序，则输入NO以后直接结束程序。

 

 

C++代码（不使用STL）：

#include <iostream>

using namespace std;

int maxn=1000;

 

void push(int stack[1100], int &top, int x)

{

    if (top>maxn)

        cout<<“overflow”;

    else

    {

        top++;

        stack[top] = x;

    }

}

void pop(int stack[1100], int &top, int &y)

{

    if (top==0)

        cout<<“downflow”;

    else

    {

        y=stack[top];

        top–;

    }

}

 

int main()

{

    int stack[1100];

    int top=0;

    int n; cin>>n;

    int a[1100];

    int cnt=0;

    for (int i=1; i<=n; ++i)

    {

        cin>>a[i];

        while (cnt<a[i])

        {

            cnt++;

            push(stack,top,cnt);

        }

        if (stack[top]!=a[i])

        {

            cout<<“NO”;

            return 0;

        }

        int y;

        pop(stack,top,y);

    }

    cout<<“YES”;

    return 0;

}

 

 

 

 

2.车厢调度

题目描述

小明在你的帮助下，破密了Ferrari设的密码门，正要往前走，突然又出现了一个密码门，门上有一个后缀表达式，其中只有“0-9”，“+”，“-”，“*”，“/”，“^”求出的值就是密码。小明对后缀表达式不太了解，还需你帮他的忙。(“/”用整数除法)

后缀表达式是符号在值之后的表达式

例如原本的3 * 4 用后缀表达式表示就是 3 4 *

后缀表达式是不存在括号的，因为必定是临近的两个值进行运算

例如 (3 + 4) * 7 写成后缀表达式就是 3 4 + 7 *

就是先计算 3 + 4 然后结果和7相乘

输入

输入共1行，为一个算式。算式长度<=100

算式的每个符号、数字用一个空格隔开，保证输入的算式正确

输出

输出共1行，就是密码。

样例输入：                      样例输出：

3 4 + 7 * 5 / 2 3 ^ +        17

 

 

题目解析：

    该题为求后缀表达式（其中式中数字均为一位数字），则对于输入不需要特殊处理，根据题意遇一个数字字符直接当作一个数字使用即可。

    将每个数字及每个运算符都记为一个单独的元素。对输入的字符串s的第1、3、5、7……、strlen(s)个字符依次遍历，若遇数字则入栈（待运算）。若遇运算符则出栈两个元素进行相应运算，并将运算结果入栈。最终栈内仅剩的一个元素（即遍历完字符串的每个字符后）即为最终所求解。

    在这里要注意建立的栈必须是数字类型而非字符类型，因为两个一位数相运算可能变成多位数。

 

 

C++代码（不使用STL）：

#include <iostream>

#include <cstring>

using namespace std;

int maxn=1000;

 

void push(int stack[1100], int &top, int x)

{

    if (top>maxn)

        cout<<“overflow”;

    else

    {

        top++;

        stack[top] = x;

    }

}

void pop(int stack[1100], int &top, int &y)

{

    if (top==0)

        cout<<“downflow”;

    else

    {

        y=stack[top];

        top–;

    }

}

 

int main()

{

    int stack[1100];

    int top=0;

    char s[1000];

    cin.get(s,1000);

    for (int i=0; i<strlen(s); i+=2)

    {

        if ((s[i]>=’0′)&&(s[i]<=’9′))

            push(stack,top,s[i]-‘0’);

        else

        {

            int x,y;

            pop(stack,top,y);

            pop(stack,top,x);

            int z;

            if (s[i]==’+’) z=x+y;

            if (s[i]==’-‘) z=x-y;

            if (s[i]==’*’) z=x*y;

            if (s[i]==’/’) z=x/y;

            if (s[i]==’^’)

            {

                z=1;

                for (int j=1; j<=y; ++j)

                    z*=x;

            }

            push(stack,top,z);

        }

    }

    cout<<stack[top];

    return 0;

}

 

 

 

 

3.括弧匹配检验

题目描述

假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，如（［ ］（））或［（［ ］［ ］）］等为正确的匹配，［（ ]）或（［ ］（ ）或 ( ( ) ) ）均为错误的匹配。

现在的问题是，要求检验一个给定表达式中的括弧是否正确匹配？

输入一个只包含圆括号和方括号的字符串，判断字符串中的括号是否匹配，匹配就输出 “OK” ，不匹配就输出“Wrong”。

输入

输入仅一行字符（字符个数小于255）

输出

匹配就输出 “OK” ，不匹配就输出“Wrong”。

样例输入：                      样例输出：

[(])                                 Wrong

 

 

题目解析：

    该题为将括号正确匹配。根据常识以及题目描述，我们可以知道正确的括号匹配即所谓“最内层”的一对括号为相同类型的括号。换一种表述方式，即为对于一个右括号来说，它需要匹配左边距离它最近的未匹配过的左括号。如果该左括号与右括号类型相同，则匹配成功，否则直接可以输出“Wrong”并结束程序。

    当考虑程序实现时，可以发现“左边最近的未匹配过的”与栈中的栈顶元素含义类似。当我们在栈中只储存左括号，并将栈中的元素定义为“未匹配过的左括号”时，可以发现因为从字符串的左边开始遍历且先遍历到的左括号先压入栈内，则栈顶元素即为“最近的”未匹配过的元素。而若栈顶的左括号该轮需要被匹配，则将其出栈。此时整个程序的实现已大致有了思路，即遍历整个字符串，若遇到左括号，无论类型都将其入栈；当遇到右括号时，则与栈顶元素相匹配。若匹配成功，则出栈栈顶元素并继续遍历字符串。若匹配不成功，则直接输出“Wrong”。

    那么我们可以总结得到：1.若某次右括号匹配类型不对应，则输出Wrong并结束程序； 2.若某次右括号匹配时栈已空，说明右括号没有相应左括号匹配，则输出Wrong并结束程序； 3.若遍历完字符串后栈中还有元素，说明有左括号没有右括号匹配，输出Wrong（自然地结束程序）； 4.若遍历完后栈空，则输出OK（自然地结束程序）。

 

 

C++代码（不使用STL）：

#include <iostream>

#include <cstring>

using namespace std;

int maxn=1000;

 

void push(char stack[1100], int &top, char x)

{

    if (top>maxn)

        cout<<“overflow”;

    else

    {

        top++;

        stack[top] = x;

    }

}

void pop(char stack[1100], int &top, char &y)

{

    if (top==0)

        cout<<“downflow”;

    else

    {

        y=stack[top];

        top–;

    }

}

 

int main()

{

    char stack[1100];

    int top=0;char y;

    char s[1000];

    cin.get(s,1000);

    for (int i=0; i<strlen(s); ++i)

    {

        if ((s[i]=='(‘)||(s[i]=='[‘))

            push(stack,top,s[i]);

        if (s[i]==’)’)

            if ((top==0)||(stack[top]=='[‘))

            {

                cout<<“Wrong”;

                return 0;

            }

        else

                pop(stack,top,y);

        if (s[i]==’]’)

            if ((top==0)||(stack[top]=='(‘))

            {

                cout<<“Wrong”;

                return 0;

            }

            else

                pop(stack,top,y);

    }

    if (top>0)

        cout<<“Wrong”;

    else

        cout<<“OK”;

    return 0;

}