Lambda Calculus

The ﬁrst line of the input contains a positive integer T denoting the number of test cases. Then T lines follow, each line contains a nonempty string denoting a lambda term.

Each variable in the the lambda terms contains only latin letters and the hyphen, and is no longer than 20 characters.

It is guaranteed that all lambda terms in the input are valid, and the total length of all lambda terms will not exceed 10⁷.

There might be some extra spaces in the input as long as they do not cause any misunderstanding.

For each test case, output ﬁrst the case number and then all distinct variables that occur free in the lambda term in a single line. These variables should be printed in lexicographic order, and there should be a single space between each two adjacent variables. There should be a space after the colon in each test case.

C++ 解法, 执行用时: 25ms, 内存消耗: 9380K, 提交时间: 2021-09-29 00:58:53

#include <functional>
#include <iostream>
#include <memory>
#include <set>
#include <string>
#include <utility>
#include <vector>

void assert(bool f) {
  if (!f) while(1);
}

std::set<std::string> freeVar;

struct Parser {
  const std::string& str;
  int i = 0;
  std::multiset<std::string> context;

  Parser(const std::string& str) : str(str) {}

  void space() {
    while (i < str.length() && str[i] == ' ') i++;
  }

  std::string var() {
    space();
    std::string v;
    while (i < str.length() && str[i] != '(' && str[i] != ')' && str[i] != ' ') {
      v += str[i++];
    }
    space();
    return v;
  }

  void app() {
    space();
    term();
    space();
    term();
    space();
  }

  void term() {
    if (str[i] == '(') {
      i++;
      space();
      int old = i;
      std::string v = var();
      if (v == "lambda") {
        assert(str[i++] == '(');
        space();
        v = var();
        assert(str[i++] == ')');
        space();
        context.insert(v);
        term();
        context.erase(context.find(v));
        assert(str[i++] == ')');
        space();
      } else {
        i = old;
        app();
        assert(str[i++] == ')');
        space();
      }
    } else {
      std::string v = var();
      assert(v.length() != 0);
      if (!context.count(v)) {
        freeVar.insert(v);
      }
    }
  }

  void run() {
    space();
    term();
    space();
    assert(i == str.length());
  }
};

int main() {
  std::ios::sync_with_stdio(false);
  int T;
  std::cin >> T;
  std::cin.ignore();
  for (int kase = 1; kase <= T; kase++) {
    std::string code;
    std::getline(std::cin, code);
    freeVar.clear();
    auto p = Parser(code);
    p.run();
    std::cout << "Case #" << kase << ":";
    for (auto& v : freeVar) std::cout << ' ' << v;
    if (freeVar.empty()) std::cout << ' ';
    std::cout << '\n';
  }
  return 0;
}

C++14(g++5.4) 解法, 执行用时: 75ms, 内存消耗: 24028K, 提交时间: 2018-10-07 14:14:13

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e7+10;

int n;
char s[maxn];

set<string>ans;
set<pair<string,int> >SET;

string getname(int &start){
	string t="";
	while(start<n&&(s[start]>='a'&&s[start]<='z'||
				s[start]>='A'&&s[start]<='Z'||
				s[start]=='-'))t.push_back(s[start++]);
	return t;
}

void eatspace(int &start){
	while(start<n&&s[start]==' ')start++;
}

void DFS(int deep,int &start){
	while(start<n){
		eatspace(start);
		if(start>=n)return;
		if(s[start]=='('){
			start++;
			DFS(deep+1,start);
		}
		else if(s[start]==')'){
			start++;
			return;
		}
		else{
			string name=getname(start);
			if(name=="lambda"){
				eatspace(start);
				if(start>=n)return;
				start++;// (
				eatspace(start);
				if(start>=n)return;
				string know=getname(start);
				SET.insert(make_pair(know,deep));
				eatspace(start);
				if(start>=n)return;
				start++;// )
				DFS(deep,start);
				SET.erase(make_pair(know,deep));
			}
			else{
				int flag=0;
				for(int i=deep;i>=0;i--)if(SET.count(make_pair(name,i))){flag=1;break;}
				if(!flag)ans.insert(name);
			}
		}
	}
}


void gao(int kase){
	SET.clear();
	ans.clear();
	fgets(s,maxn,stdin);

	n=strlen(s)-1;
	int start=0;
	DFS(0,start);
	printf("Case #%d:",kase);
	if(!ans.size())printf(" ");
	for(string t:ans)printf(" %s",t.c_str());
	printf("\n");
}

int main(){
	int T;
	scanf("%d\n",&T);
	for(int i=1;i<=T;i++)gao(i);
	return 0;
}

详情