S式の要素を走査する

再帰とループの2通りの方法でS式（リスト）を走査してみる。ループの方はスタックの使い方これでいいのかよくわからんけど。

using System;
using System.Collections.Generic;

abstract class SExp { }

class Pair : SExp
{
  public SExp Car { get; private set; }
  public SExp Cdr { get; private set; }

  public Pair(SExp car, SExp cdr)
  {
    this.Car = car;
    this.Cdr = cdr;
  }

  public override string ToString()
  {
    return "(" + this.Car + " . " + this.Cdr + ")";
  }
}

class Atom : SExp
{
  public string Value { get; set; }

  public Atom(string str)
  {
    this.Value = str;
  }

  public override string ToString()
  {
    return this.Value;
  }
}

class Nil : SExp 
{
  public override string ToString()
  {
    return "()";
  }
}

class App
{
  static void Main(string[] args)
  {
    // exp2 == (x y (a b c) z)
    SExp exp1 = new Pair(new Atom("a"), new Pair(new Atom("b"), new Pair(new Atom("c"), new Nil())));
    SExp exp2 = new Pair(new Atom("x"), new Pair(new Atom("y"), new Pair(exp1, new Pair(new Atom("z"), new Nil()))));

    Scan1(exp2);
    Console.WriteLine("==========");
    Scan2(exp2);
  }

  // 再帰処理で走査
  static void Scan1(SExp exp)
  {
    if (exp is Pair)
    {
      Scan1((exp as Pair).Car);
      Scan1((exp as Pair).Cdr);
    }
    else
    {
      Console.WriteLine(exp);
    }
  }

  // ループ+スタックで走査
  static void Scan2(SExp exp)
  {
    Stack<SExp> cs = new Stack<SExp>();
    while (true)
    {
      if (exp is Pair)
      {
        SExp car = (exp as Pair).Car;
        SExp cdr = (exp as Pair).Cdr;
        cs.Push(cdr);
        exp = car;
      }
      else
      {
        Console.WriteLine(exp);
        if (0 == cs.Count) break;
        exp = cs.Pop();
      }
    }
  }
}

car部にPairがくると木構造（？）になってしまう。car部の部分木を走査し終わった後にcdr部の部分木を走査するためには、位置を記憶しておかないといけないので、スタックが必要になる。メソッド呼び出しは、この「戻ってくる場所をスタックで記憶しておく」という仕事を処理系が裏でやってくれるので簡潔に書ける。

以前二分木のイテレータで散々悩んだときのやり方でも考えてみるかな。S式も木構造だけど、あの時の木構造と違うのは、ノードが「自分の値」を持っていない（leftとrightだけ）ってことなのかな？