Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
C# Abstract Syntax Tree Example: Compiler for a numeric expression
//Rextester.Program.Main is the entry point for your code. Don't change it. //Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5 using System; using System.Collections.Generic; using System.Linq; using System.Text.RegularExpressions; using System.Runtime.Serialization; using System.Text; namespace Rextester { public class Program { public static void Main(string[] args) { string input = string.Empty; Console.WriteLine("Input an expression, for example: (2.11*-3*(5+7.18+9.23))+---1+++(-+-+--(1+2))*(-+-3+4)*(5+6)+3*(2+1)"); input = "(2.11*-3*(5+7.18+9.23))+---1+++(-+-+--(1+2))*(-+-3+4)*(5+6)+3*(2+1)"; //while (true) { //Console.WriteLine(); //Console.Write("Input (q = quit): "); //FlushConsole(); //input = Console.ReadLine(); //if (input == "q") //{ // break; //} try { Parser interpreter = new Parser(input); Expression node = interpreter.Parse(); Console.WriteLine(string.Format("Tree graph:{0}{1}", Environment.NewLine, node.Accept(new GraphBuilder()))); Console.WriteLine(string.Format("Value: {0}", node.Accept(new ValueBuilder()))); Console.WriteLine(string.Format("Lisp form: {0}", node.Accept(new LispFormBuilder()))); } catch (InvalidSyntaxException ex) { Console.WriteLine(ex.Message); } catch (Exception ex) { Console.WriteLine(ex); } } } static void FlushConsole() { while (Console.KeyAvailable) { Console.ReadKey(false); } } } internal class Parser { private Token curToken; private int curPos; private int charCount; private char curChar; public string Text { get; private set; } public Parser(string text) { this.Text = string.IsNullOrEmpty(text) ? string.Empty : text; this.charCount = this.Text.Length; this.curToken = Token.None(); this.curPos = -1; this.Advance(); } internal Expression Parse() { this.NextToken(); Expression node = this.GrabExpr(); this.ExpectToken(TokenType.None); return node; } private Token ExpectToken(TokenType tokenType) { if (this.curToken.Type == tokenType) { return this.curToken; } else { throw new InvalidSyntaxException(string.Format("Invalid syntax at position {0}. Expected {1} but {2} is given.", this.curPos, tokenType, this.curToken.Type.ToString())); } } private Expression GrabExpr() { Expression left = this.GrabTerm(); while (this.curToken.Type == TokenType.Plus || this.curToken.Type == TokenType.Minus) { Token op = this.curToken; this.NextToken(); Expression right = this.GrabTerm(); left = new BinOp(op, left, right); } return left; } private Expression GrabTerm() { Expression left = this.GrabFactor(); while (this.curToken.Type == TokenType.Multiply || this.curToken.Type == TokenType.Divide) { Token op = this.curToken; this.NextToken(); Expression right = this.GrabFactor(); left = new BinOp(op, left, right); } return left; } private Expression GrabFactor() { if (this.curToken.Type == TokenType.Plus || this.curToken.Type == TokenType.Minus) { Expression node = this.GrabUnaryExpr(); return node; } else if (this.curToken.Type == TokenType.LeftParenthesis) { Expression node = this.GrabBracketExpr(); return node; } else { Token token = this.ExpectToken(TokenType.Number); this.NextToken(); return new Num(token); } } private Expression GrabUnaryExpr() { Token op; if (this.curToken.Type == TokenType.Plus) { op = this.ExpectToken(TokenType.Plus); } else { op = this.ExpectToken(TokenType.Minus); } this.NextToken(); if (this.curToken.Type == TokenType.Plus || this.curToken.Type == TokenType.Minus) { Expression expr = this.GrabUnaryExpr(); return new UnaryOp(op, expr); } else { Expression expr = this.GrabFactor(); return new UnaryOp(op, expr); } } private Expression GrabBracketExpr() { this.ExpectToken(TokenType.LeftParenthesis); this.NextToken(); Expression node = this.GrabExpr(); this.ExpectToken(TokenType.RightParenthesis); this.NextToken(); return node; } private void NextToken() { if (this.curChar == char.MinValue) { this.curToken = Token.None(); return; } if (this.curChar == ' ') { while (this.curChar != char.MinValue && this.curChar == ' ') { this.Advance(); } if (this.curChar == char.MinValue) { this.curToken = Token.None(); return; } } if (this.curChar == '+') { this.curToken = new Token(TokenType.Plus, this.curChar.ToString()); this.Advance(); return; } if (this.curChar == '-') { this.curToken = new Token(TokenType.Minus, this.curChar.ToString()); this.Advance(); return; } if (this.curChar == '*') { this.curToken = new Token(TokenType.Multiply, this.curChar.ToString()); this.Advance(); return; } if (this.curChar == '/') { this.curToken = new Token(TokenType.Divide, this.curChar.ToString()); this.Advance(); return; } if (this.curChar == '(') { this.curToken = new Token(TokenType.LeftParenthesis, this.curChar.ToString()); this.Advance(); return; } if (this.curChar == ')') { this.curToken = new Token(TokenType.RightParenthesis, this.curChar.ToString()); this.Advance(); return; } if (this.curChar >= '0' && this.curChar <= '9') { string num = string.Empty; while (this.curChar >= '0' && this.curChar <= '9') { num += this.curChar.ToString(); this.Advance(); } if (this.curChar == '.') { num += this.curChar.ToString(); this.Advance(); if (this.curChar >= '0' && this.curChar <= '9') { while (this.curChar >= '0' && this.curChar <= '9') { num += this.curChar.ToString(); this.Advance(); } } else { throw new InvalidSyntaxException(string.Format("Invalid syntax at position {0}. Unexpected symbol {1}.", this.curPos, this.curChar)); } } this.curToken = new Token(TokenType.Number, num); return; } throw new InvalidSyntaxException(string.Format("Invalid syntax at position {0}. Unexpected symbol {1}.", this.curPos, this.curChar)); } private void Advance() { this.curPos += 1; if (this.curPos < this.charCount) { this.curChar = this.Text[this.curPos]; } else { this.curChar = char.MinValue; } } } [Serializable] internal class InvalidSyntaxException : Exception { public InvalidSyntaxException() { } public InvalidSyntaxException(string message) : base(message) { } public InvalidSyntaxException(string message, Exception innerException) : base(message, innerException) { } protected InvalidSyntaxException(SerializationInfo info, StreamingContext context) : base(info, context) { } } internal class GraphBuilder : INodeVisitor { private static string ReplaceLastChar(string str, char rep = ' ') { if (!string.IsNullOrEmpty(str)) { return str.Substring(0, str.Length - 1) + rep.ToString(); } else { return ""; } } const Char SPACE = ' '; const Char L_TURN = '┌'; const Char V_PIPE = '│'; const Char R_TURN = '└'; const string TAB = " "; const string H_PIPE = "──"; private StringBuilder sb; private Stack<string> indentStack; private Stack<BranchOriental> orientalStack; public GraphBuilder() { this.sb = new StringBuilder(); this.indentStack = new Stack<string>(); this.orientalStack = new Stack<BranchOriental>(); this.indentStack.Push(string.Empty); this.orientalStack.Push(BranchOriental.None); } public object VisitBinOp(Token op, INode left, INode right) { BranchOriental legacyOriental = this.orientalStack.Pop(); string legacyIndent = this.indentStack.Pop(); if (legacyOriental == BranchOriental.Left) { this.indentStack.Push(ReplaceLastChar(legacyIndent, SPACE) + TAB + L_TURN); this.orientalStack.Push(BranchOriental.Left); left.Accept(this); } else { this.indentStack.Push(ReplaceLastChar(legacyIndent, V_PIPE) + TAB + V_PIPE); this.orientalStack.Push(BranchOriental.Left); left.Accept(this); } if (legacyOriental == BranchOriental.Left) { sb.AppendLine(ReplaceLastChar(legacyIndent, L_TURN) + H_PIPE + " (" + op.ToString() + ")"); } else { sb.AppendLine(ReplaceLastChar(legacyIndent, R_TURN) + H_PIPE + " (" + op.ToString() + ")"); } if (legacyOriental == BranchOriental.Right) { this.indentStack.Push(ReplaceLastChar(legacyIndent, SPACE) + TAB + R_TURN); this.orientalStack.Push(BranchOriental.Right); right.Accept(this); } else { this.indentStack.Push(ReplaceLastChar(legacyIndent, V_PIPE) + TAB + V_PIPE); this.orientalStack.Push(BranchOriental.Right); right.Accept(this); } return this.sb.ToString(); } public object VisitNum(Token num) { BranchOriental legacyOriental = this.orientalStack.Pop(); string legacyIndent = this.indentStack.Pop(); if (legacyOriental == BranchOriental.Left) { sb.AppendLine(ReplaceLastChar(legacyIndent, L_TURN) + H_PIPE + " " + num.ToString()); } else { sb.AppendLine(ReplaceLastChar(legacyIndent, R_TURN) + H_PIPE + " " + num.ToString()); } return this.sb.ToString(); } public object VisitUnaryOp(Token op, INode node) { BranchOriental legacyOriental = this.orientalStack.Pop(); string legacyIndent = this.indentStack.Pop(); if (legacyOriental == BranchOriental.Left) { sb.AppendLine(ReplaceLastChar(legacyIndent, L_TURN) + H_PIPE + " (" + op.ToString() + ")"); } else { sb.AppendLine(ReplaceLastChar(legacyIndent, R_TURN) + H_PIPE + " (" + op.ToString() + ")"); } if (legacyOriental == BranchOriental.Right) { this.indentStack.Push(ReplaceLastChar(legacyIndent, SPACE) + TAB + R_TURN); this.orientalStack.Push(BranchOriental.Right); node.Accept(this); } else { this.indentStack.Push(ReplaceLastChar(legacyIndent, V_PIPE) + TAB + R_TURN); this.orientalStack.Push(BranchOriental.Right); node.Accept(this); } return this.sb.ToString(); } internal enum BranchOriental { None, Left, Right } } internal class ValueBuilder : INodeVisitor { public object VisitBinOp(Token op, INode left, INode right) { switch (op.Type) { case TokenType.Plus: return (decimal)left.Accept(this) + (decimal)right.Accept(this); case TokenType.Minus: return (decimal)left.Accept(this) - (decimal)right.Accept(this); case TokenType.Multiply: return (decimal)left.Accept(this) * (decimal)right.Accept(this); case TokenType.Divide: return (decimal)left.Accept(this) / (decimal)right.Accept(this); default: throw new Exception(string.Format("Token of type {0} cannot be evaluated.", op.Type.ToString())); } } public object VisitNum(Token num) { return decimal.Parse(num.Value); } public object VisitUnaryOp(Token op, INode node) { switch (op.Type) { case TokenType.Plus: return (decimal)node.Accept(this); case TokenType.Minus: return -(decimal)node.Accept(this); default: throw new Exception(string.Format("Token of type {0} cannot be evaluated.", op.Type.ToString())); } } } internal class LispFormBuilder : INodeVisitor { public object VisitBinOp(Token op, INode left, INode right) { return "(" + op.ToString() + " " + left.Accept(this) + " " + right.Accept(this) + ")"; } public object VisitNum(Token num) { return num.ToString(); } public object VisitUnaryOp(Token op, INode node) { return "(" + op.ToString() + " " + node.Accept(this) + ")"; } } internal interface INode { object Accept(INodeVisitor visitor); } internal interface INodeVisitor { object VisitNum(Token num); object VisitUnaryOp(Token op, INode node); object VisitBinOp(Token op, INode left, INode right); } internal abstract class Expression : INode { abstract public object Accept(INodeVisitor visitor); } internal class Num : Expression { internal Token Token { get; private set; } public Num(Token token) { this.Token = token; } override public object Accept(INodeVisitor visitor) { return visitor.VisitNum(this.Token); } } internal class UnaryOp : Expression { internal Token Op { get; private set; } internal Expression Node { get; private set; } public UnaryOp(Token op, Expression node) { this.Op = op; this.Node = node; } override public object Accept(INodeVisitor visitor) { return visitor.VisitUnaryOp(this.Op, this.Node); } } internal class BinOp : Expression { internal Token Op { get; private set; } internal Expression Left { get; private set; } internal Expression Right { get; private set; } public BinOp(Token op, Expression left, Expression right) { this.Op = op; this.Left = left; this.Right = right; } override public object Accept(INodeVisitor visitor) { return visitor.VisitBinOp(this.Op, this.Left, this.Right); } } internal class Token { public TokenType Type { get; private set; } public string Value { get; private set; } public Token(TokenType type, string value) { this.Type = type; this.Value = value; } internal static Token None() { return new Token(TokenType.None, ""); } public override string ToString() { return this.Value; } } internal enum TokenType { None, Plus, Minus, Multiply, Divide, Number, LeftParenthesis, RightParenthesis } }
run
|
edit
|
history
|
help
2
TestApp
Chest Interaction Unity
Plt-D v.0.9.4
SHA Tester 2.0
c++
Testing 10
PassByValue vs PassByRerefence
Binary Search Tree
OneAwayString
Problem 5 SingleDigit