An example of how to do syntax tree construction without using return values

StackMachineTreeConstruction

using System;
using System.Collections.Generic;
using System.Text;

namespace StackMachineTreeConstruction
{
  public class Class1
  {
    enum TokenType
    {
      None,
      Number,
      Operator,
      LeftParen,
      RightParen
    }

    struct Token
    {
      public readonly TokenType Type;
      public readonly string Text;

      public Token(TokenType type, string text)
      {
        this.Type = type;
        this.Text = text;
      }
    }

    static IEnumerable<Token> GetInputStream()
    {
      yield return new Token(TokenType.Number, "1");
      yield return new Token(TokenType.Operator, "+");
      yield return new Token(TokenType.Number, "2");
    }

    static IEnumerable<Token> GetInputStream2()
    {
      yield return new Token(TokenType.Number, "1");
      yield return new Token(TokenType.Operator, "+");
      yield return new Token(TokenType.LeftParen, "(");
      yield return new Token(TokenType.Number, "2");
      yield return new Token(TokenType.Operator, "-");
      yield return new Token(TokenType.Number, "3");
      yield return new Token(TokenType.RightParen, ")");
    }

    static IEnumerable<Token> GetInputStream3()
    {
      yield return new Token(TokenType.LeftParen, "(");
      yield return new Token(TokenType.Number, "2");
      yield return new Token(TokenType.Operator, "-");
      yield return new Token(TokenType.Number, "3");
      yield return new Token(TokenType.RightParen, ")");
      yield return new Token(TokenType.Operator, "+");
      yield return new Token(TokenType.Number, "1");
    }

    abstract class SyntaxTree
    {
      protected SyntaxTree()
      {
      }

      public override string ToString()
      {
        var sb = new StringBuilder();
        ToString(sb, 0);
        return sb.ToString();
      }

      public abstract void ToString(StringBuilder sb, int indent);
    }

    class SyntaxNode : SyntaxTree
    {
      public readonly string NodeName;
      public readonly List<SyntaxTree> Children;
      public SyntaxNode(string nodeName)
      {
        this.NodeName = nodeName;
        this.Children = new List<SyntaxTree>();
      }

      public override void ToString(StringBuilder sb, int indent)
      {
        sb.Append('(');
        sb.Append(NodeName);
        if (Children.Count <= 1)
        {
          foreach (var child in Children)
          {
            sb.Append(' ');
            child.ToString(sb, indent);
          }
        }
        else
        {
          foreach (var child in Children)
          {
            sb.AppendLine().Append(' ', indent + 1);
            child.ToString(sb, indent + 1);
          }
          sb.AppendLine().Append(' ', indent);
        }
        sb.Append(')');
      }
    }

    class TokenNode : SyntaxTree
    {
      public readonly Token Token;
      public TokenNode(Token token)
      {
        Token = token;
      }

      public override void ToString(StringBuilder sb, int indent)
      {
        sb.Append('"').Append(Token.Text).Append('"');
      }
    }

    class ParserBase
    {
      private readonly IEnumerator<Token> _inputStream;
      private readonly List<SyntaxTree> _stack;

      public SyntaxTree SyntaxTree { get { return _stack[_stack.Count - 1]; } }

      public ParserBase(IEnumerable<Token> inputStream)
      {
        _inputStream = inputStream.GetEnumerator();
        _stack = new List<Class1.SyntaxTree>();
        Read();
      }

      private Token _token;

      private void Read()
      {
        if (_inputStream.MoveNext())
        {
          _token = _inputStream.Current;
        }
        else
        {
          _token = default(Token);
        }
      }

      protected bool Accept(TokenType type)
      {
        if (_token.Type == type)
        {
          _stack.Add(new TokenNode(_token)); // push
          Read();
          return true;
        }
        return false;
      }

      protected void Reduce(int nodeCount, string nodeName)
      {
        var tree = new SyntaxNode(nodeName);
        for (int i = 0; i < nodeCount; i++)
        {
          tree.Children.Add(_stack[_stack.Count - nodeCount + i]); // reverse pop
        }
        for (int i = 0; i < nodeCount; i++)
        {
          _stack.RemoveAt(_stack.Count - 1);
        }
        _stack.Add(tree);
      }
    }

    class Parser : ParserBase
    {
      public Parser(IEnumerable<Token> inputStream)
        : base(inputStream)
      {
      }

      public void Expression()
      {
        Primary();
        if (Accept(TokenType.Operator))
        {
          Expression();
          Reduce(3, "BinaryExpression");
          return;
        }
      }

      public void Primary()
      {
        if (Accept(TokenType.Number))
        {
          Reduce(1, "NumberLiteral");
          return;
        }
        if (Accept(TokenType.LeftParen))
        {
          Expression();
          if (!Accept(TokenType.RightParen))
          {
            throw new InvalidOperationException();
          }
          Reduce(3, "EvalExpression");
          return;
        }
      }
    }

    public static void Main()
    {
      WriteLine(GetInputStream());
      WriteLine(GetInputStream2());
      WriteLine(GetInputStream3());
    }

    private static void WriteLine(IEnumerable<Token> inputStream)
    {
      var i = 0;
      foreach (var token in inputStream)
      {
        if (i > 0)
        {
          Console.Write(" -> ");
        }
        Console.Write("{0}", token.Type);
        i++;
      }
      Console.WriteLine();
      var parser = new Parser(inputStream);
      parser.Expression();
      Console.WriteLine(parser.SyntaxTree);
      Console.WriteLine();
    }
  }
}