首页 > ACM题库 > HDU-杭电 > HDU 3528-The Simple Programming Language[解题报告]HOJ
2014
11-05

HDU 3528-The Simple Programming Language[解题报告]HOJ

The Simple Programming Language

问题描述 :

Consider the following programming language. This language contains only two types of statements: simple statements and compound statements. The simple statement is in the form “write (literal)”, where “write” is a key word indicating that the content of the literal should be written to the standard output. The content of literals is surrounded by a pair of double quotes. The compound statement is in the form “if (<expression>) <statement>” or “if (<expression>) <statement> else <statement>”. Here “if” and “else” are key words and “expression” can be either “1” or “0” indicating “true” or “false”. Statement can be either compound or simple, which means compound statements can be nested. Note that each “else” should match the nearest “if”.

输入:

The input has multiple test cases. Every test case is exactly a statement. Every test case is ended with an empty line and there will be no empty lines within a statement. Please pay attention that empty lines separate the statements and adjacent statements are independent of each other.

输出:

The input has multiple test cases. Every test case is exactly a statement. Every test case is ended with an empty line and there will be no empty lines within a statement. Please pay attention that empty lines separate the statements and adjacent statements are independent of each other.

样例输入:

write(“q”)

if(0) write(“x”) else write(“y”)

if(1) if(0) write(“x”) else write(“y”)

if(0) if(0) write(“x”) else write(“y”)

样例输出:

q
y
y

Hint
The 4th test case has no output.

#include <cstdio>
#include <cstring>
#include <cctype>
#define MAX_LEN 1000010

char buf[MAX_LEN];

char *ignore(char *p) {
	while (*p && isspace (*p)) ++p;
	return p;
}

int main() {
	while (gets(buf)) {
		char *p = buf + strlen(buf);
		while (gets(p) != NULL, *p) {
			p += strlen(p);
		}
		p = buf;
		//puts(buf);
		while (*p) {
			p = ignore(p);
			if (*p == 'w') {
				p += 7;
				while (*p != '"') {
					putchar(*p);
					++p;
				}
				puts("");
				break;
			}
			p += 3;
			if (*p == '1') p += 2;
			else {
				p += 2;
				int cnt = 1;
				while (*p && cnt) {
					p = ignore(p);
					if (*p == 'w') {
						while (*p != ')') ++p;
						++p;
						continue;
					}
					if (*p == 'i') {
						++cnt;
						p += 5;
						continue;
					}
					if (*p == 'e') {
						--cnt;
						p += 4;
						continue;
					}
				}
			}
		}
	}
	return 0;
}

  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c