2-2 列车厢调度

分数 5

作者 周强

单位 青岛大学

       1  ======   <--移动方向
        /
3 =====  
        \
       2  ======   -->移动方向

大家或许在某些数据结构教材上见到过“列车厢调度问题”（当然没见过也不要紧）。今天，我们就来实际操作一下列车厢的调度。对照上方的ASCII字符图，问题描述如下：

有三条平行的列车轨道（1、2、3）以及1-3和2-3两段连接轨道。现有一列车厢停在1号轨道上，请利用两条连接轨道以及3号轨道，将车厢按照要求的顺序转移到2号轨道。规则是：

  • 每次转移1节车厢；
  • 处在1号轨道的车厢要么经过1-3连接道进入3号轨道（该操作记为"1->3"），要么经过两条连接轨道直接进入2号轨道（该操作记为"1->2"）；
  • 一旦车厢进入2号轨道，就不可以再移出该轨道；
  • 处在3号轨道的车厢，只能经过2-3连接道进入2号轨道（该操作记为"3->2"）；
  • 显然，任何车厢不能穿过、跨越或绕过其它车厢进行移动。

对于给定的1号停车顺序，如果经过调度能够实现2号轨道要求的顺序，则给出操作序列；如果不能，就反问用户 Are(你) you(是) kidding(凯丁) me(么)?

输入格式:

两行由大写字母组成的非空字符串，第一行表示停在1号轨道上的车厢从左到右的顺序，第二行表示要求车厢停到2号轨道的进道顺序（输入样例1中第二行CBA表示车厢在2号轨道的停放从左到右是ABC，因为C最先进入，所以在最右边）。两行字符串长度相同且不超过26（因为只有26个大写字母），每个字母表示一节车厢。题目保证同一行内的字母不重复且两行的字母集相同。

输出格式:

如果能够成功调度，给出最短的操作序列，每个操作占一行。所谓“最短”，即如果1->2可以完成的调度，就不要通过1->3和3->2来实现。如果不能调度，输出 “Are you kidding me?”

输入样例1:

ABC
CBA

输出样例1:

1->3
1->3
1->2
3->2
3->2

输入样例2:

ABC
CAB

输出样例2:

Are you kidding me?

解析

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
	string s1, s2;
	cin >> s1 >> s2;//这是一轨道和二轨道
	
	stack<char> third;//三轨道是一个栈
	string result[100];//这是最后操作的结果

	//接下来是思路
	//1 号轨道车厢从左到右依次可移动，3 号轨道为先进后出的栈
	//（暂存车厢），2 号轨道为最终目标（进入后不可移出）
	//。需按输入第二行的 “进道顺序” 将车厢送入 2 号轨道，
	//且操作序列最短。

	//优先检查 3 号轨道（栈顶）是否为当前需进入 2 号的车厢，
	//是则直接转移（3->2）。

	//若 3 号轨道无目标车厢，检查 1 号轨道当前车厢：
	// 是目标则直接转移（1->2），否则暂存到 3 号轨道（1->3）。

	//若 1 号轨道无车厢且 3 号轨道无目标车厢，调度失败。

	int count = 0;//用于记录result
	int i = 0;//一轨道的指针
	int j = 0;//二轨道的指针

	while (j < s2.length()) {
		if (third.empty() != 1 && third.top() == s2[j]) {
			result[count] = "3->2";
			count++;
			third.pop();
			j++;
			continue;
		}
		if (i < s1.length() && s1[i] == s2[j]) {
			result[count] = "1->2";
			i++;
			j++;
			count++;
		}
		else if (i < s1.length())
		{
			result[count] = "1->3";
			third.push(s1[i]);
			count++;
			i++;
		}
		else {
			printf("Are you kidding me?");
			return 0;
		}
	}
	for (int i = 0; i < count; i++) {
		cout << result[i] << endl;
	}
	return 0;
}

2-3 符号配对

分数 6

作者 DS课程组

单位 浙江大学

请编写程序检查C语言源程序中下列符号是否配对：/*与*/、(与)、[与]、{与}。

输入格式:

输入为一个C语言源程序。当读到某一行中只有一个句点.和一个回车的时候，标志着输入结束。程序中需要检查配对的符号不超过100个。

输出格式:

首先，如果所有符号配对正确，则在第一行中输出YES，否则输出NO。然后在第二行中指出第一个不配对的符号：如果缺少左符号，则输出?-右符号；如果缺少右符号，则输出左符号-?。

输入样例1：

void test()
{
    int i, A[10];
    for (i=0; i<10; i++) { /*/
        A[i] = i;
}
.

输出样例1：

NO
/*-?

输入样例2：

void test()
{
    int i, A[10];
    for (i=0; i<10; i++) /**/
        A[i] = i;
}]
.

输出样例2：

NO
?-]

输入样例3：

void test()
{
    int i
    double A[10];
    for (i=0; i<10; i++) /**/
        A[i] = 0.1*i;
}
.

输出样例3：

YES

作者的第一次代码（思路是提取所有符号到symbols中，然后先判断” /* “和” */ “，因为题目是两个符号组合在一起的，所以用string存和入栈，再用singleChar(1, symbols[i])，化为char来判断其他三个符号，最后看栈里面还有没有剩下的，如果有就取栈底）

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool isMatch(const string& left, const string& right) {
	if (left == "(" && right == ")") return true;
	if (left == "[" && right == "]") return true;
	if (left == "{" && right == "}") return true;
	if (left == "/*" && right == "*/") return true;
	return false;
}

int main() {
    string symbols;  // 存储所有提取出的符号
    string line;     // 临时存储每行输入

    // 步骤1：读取输入并提取所有符号到symbols中
    //getline(cin, line)这个是读取一整行的字符
    while (getline(cin, line)) {
        if (line == ".") break;  // 输入结束标志

        int len = line.size();
        int i = 0;
        while (i < len) {
            // 提取双字符左符号"/*"
            if (line[i] == '/' && i + 1 < len && line[i + 1] == '*') {
                symbols += "/*";  // 加入符号串
                i += 2;  // 跳过下一个'*'
            }
            // 提取双字符右符号"*/"
            else if (line[i] == '*' && i + 1 < len && line[i + 1] == '/') {
                symbols += "*/";  // 加入符号串
                i += 2;  // 跳过下一个'/'
            }
            // 提取单字符左符号：(、[、{
            else if (line[i] == '(' || line[i] == '[' || line[i] == '{') {
                symbols += line[i];  // 加入符号串
                i += 1;
            }
            // 提取单字符右符号：)、]、}
            else if (line[i] == ')' || line[i] == ']' || line[i] == '}') {
                symbols += line[i];  // 加入符号串
                i += 1;
            }
            // 其他字符（非目标符号）：忽略
            else {
                i += 1;
            }
        }
    }

    //上述步骤已经把所有需要判断的符号都存进symbols里了
    //接下来建一个符号栈，开始符号配对
    stack<string> op;
    int symlen = symbols.size();
    int i = 0;
    while (i < symlen) {
        if (i + 1 < symlen) {
            string twochar = symbols.substr(i, 2);//取当前及下一个字符
            if (twochar == "/*") {//左符号：入栈
                op.push(twochar);
                i = i + 2;
                continue;
            }
            else if (twochar == "*/")
            {
                string right = "*/";
                if (op.empty() == 1) {//栈空：缺左符号
                    cout << "NO\n?-*/" << endl;
                    return 0;
                }
                string left = op.top();
                op.pop();
                if (isMatch(left, right) == false) {
                    cout << "NO\n?-*/" << endl;
                    return 0;
                }
                i = i + 2;
                continue;
            }
        }

        string singleChar(1, symbols[i]);
        if (singleChar == "(" || singleChar == "[" || singleChar == "{") {
            op.push(singleChar);
            i += 1;
        }

        else if (singleChar == ")" || singleChar == "]" || singleChar == "}") {
            if (op.empty()) {
                cout << "NO\n?-";
                cout << singleChar << endl;
                return 0;
            }
            string left = op.top();
            op.pop();
            if (isMatch(left, singleChar) != 1) {
                cout << "NO\n?-";
                cout << singleChar << endl;
                return 0;
            }
            i += 1;
        }
    }

    if (op.empty() == 1) {
        cout << "YES" << endl;
    }
    //弹出所有元素，记录栈底
    else {
        string firstleft;
        while (op.empty() != 1) {
            if (op.size() == 1) {
                firstleft = op.top();
            }
            op.pop();
        }
        cout << "NO\n" << firstleft << "-?" << endl;
        return 0;
    }
    return 0;
}

但是半对，评测详情：

测试点 提示 内存(KB) 用时(ms) 结果
0 488 2 答案错误
1 556 2 答案正确
2 304 2 答案正确
3 568 2 答案正确
4 304 2 答案正确
5 576 2 答案错误