AOJ : 2365 - Memory Leak

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2365
立命合宿のDay3で出題しました.
問題文長くてごめんなさい.

解法

構文解析やるだけです.
問題文中に, 注意すべき制約がいっぱい書いてあるので注意しましょう.
(ジャッジ側で, もっと見やすいようにまとめておけばよかったです)

プログラム

ジャッジ解です.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;

int n, idx; //メモリ上限, 文字列の添字
int max_ptr, mem; //使用済みのアドレス値+1, 現在確保しているメモリのサイズ
char s[1000002]; //文字列

int var[256]; //各変数に入っている値を格納
bool mem_flg[1000002]; //メモリ上に確保した領域が残っているかどうか
int mem_size[1000002]; //確保した領域のサイズ

int Number();
int Expr();
int Assign();
int Malloc();
bool Free();
int Clone();
bool Line();

int Number(){
  int res = 0;

  while(isdigit(s[idx])){
    res *= 10;
    res += s[idx] - '0';
    idx++;
  }

  return res;
}

int Malloc(){
  idx += 7; //"malloc("の文字数

  int tmp = Number();

  idx++; //")"の文字数

  if(n < mem + tmp){
    return 0;
  }

  mem_flg[max_ptr] = true;
  mem_size[max_ptr] = tmp;
  mem += tmp;
  max_ptr++;

  return max_ptr - 1;
}

int Assign(){
  int alpha = s[idx];

  idx += 2; //変数名と"="の文字数

  int ptr = Expr();

  return var[alpha] = ptr;
}

int Clone(){
  idx += 6; //"clone("の文字数

  int ptr = Expr();
  if(ptr == 0){
    return 0;
  }
  if(ptr == -2 || ptr == -1 || !mem_flg[ptr]){
    return -2;
  }

  idx++; //")"の文字数

  if(n < mem + mem_size[ptr]){
    return 0;
  }

  mem_flg[max_ptr] = true;
  mem_size[max_ptr] = mem_size[ptr];
  mem += mem_size[ptr];
  max_ptr++;

  return max_ptr - 1;
}

int Expr(){
  if(s[idx] == '('){
    idx++; //"("の文字数
    int tmp = Expr();
    idx++; //")"の文字数

    return tmp;
  }
  else if(s[idx] == 'N' && s[idx + 1] == 'U'){
    idx += 4; //"NULL"の文字数
    return 0;
  }
  else if(s[idx + 1] == '='){
    return Assign();
  }
  else if(s[idx] == 'm'){
    return Malloc();
  }
  else if(s[idx] == 'c'){
    return Clone();
  }
  else{
    return var[(int)s[idx++]];
  }
}

bool Free(){
  idx += 5; //"free("の文字数

  int ptr = Expr();
  if(ptr == -2 || ptr == -1){
    return false;
  }

  idx++; //")"の文字数

  if(ptr == 0){ //NULLの場合, 無視
    return true;
  }
  else{
    if(!mem_flg[ptr]){ //すでに確保領域でないならError
      return false;
    }
    mem -= mem_size[ptr];
    mem_flg[ptr] = false;
    mem_size[ptr] = 0;
    return true;
  }
}

bool Line(){
  if(s[idx] == 'f'){
    return Free();
  }
  else{
    int tmp = Expr();
    if(tmp == -2){
      return false;
    }
    return true;
  }
}

int main(){
  bool error_flg = false;

  mem = 0;
  max_ptr = 1;
  memset(var, -1, sizeof(var));
  memset(mem_flg, 0, sizeof(mem_flg));
  memset(mem_size, 0, sizeof(mem_size));

  scanf("%d", &n);

  while(scanf("%s", s) != EOF){
    if(error_flg) continue;

    idx = 0;
    error_flg = !Line();
  }

  if(error_flg){
    printf("Error\n");
  }
  else{
    int ans = 0;

    for(int i = 'A'; i <= 'Z'; i++){
      if(0 < var[i]){
	mem_flg[var[i]] = false;
      }
    }

    for(int i = 1; i < max_ptr; i++){
      if(mem_flg[i]){
	ans += mem_size[i];
      }
    }

    printf("%d\n", ans);
  }
}

ジャッジ入出力

要望があったので, コーナケースっぽい入出力を貼っておきます.

100
A=malloc(10)
B=clone(A)
free(A)
#=> 0

100
free(NULL)
#=> 0

100
A=malloc(10)
free(A)
free(A)
#=> Error

100
A=NULL
free(A)
free(A)
#=> 0

100
clone(NULL)
#=> 0

10
A=malloc(100)
B=clone(A)
free(A)
#=> 0

30
A=malloc(100)
B=malloc(10)
A=clone(A)
B=clone(B)
free(B)
free(A)
#=> 10

30
A=malloc(100)
B=malloc(50)
A=clone(A)
B=clone(B)
free(B)
free(A)
#=> 0

100
clone(B=clone(clone(D=malloc(10))))
#=>20

10
A=B
#=>0

10
clone(A)
#=> Error