imports $system = system
imports $io = system.io

global $tokens = 
			{
				LeftPara=1,
				RightPara=2,
				Star=3,
				Plus=4,
				Min=5,
				Number=6,
				Div=7,
				Var=8
			}
			
;creates context for scanner
function scanner_create($expr)
	if $system.string.isnullorempty($expr) 
		throw '$expr should not be null or empty'
	endif
	
	$scanner_create = {
			PeekToken=nothing,
			Reader = $io.StringReader($expr)
		   }
endfunction

;converts object to character
function ToChar($c)
	$ToChar = $System.Convert.ToChar($c)
endfunction

;reads token from scanner state
function scanner_read($state)
	dim $c = 0
	dim $builder = $System.Text.StringBuilder()
	dim $length = 0
	
	if $state.PeekToken <> nothing
		dim $ret = $state.PeekToken
		$state.PeekToken = nothing
		$scanner_read = $ret
		exit 0
	endif
	
	$c = $state.Reader.Read

	while $c > 0
		dim $char = ToChar($c)
		
		select
			case $System.Char.IsWhitespace($char)
				$c = $state.Reader.Read
				continue
			case $System.Char.IsNumber($char)
				$length = $builder.Append($char)
				$c = $state.Reader.Peek
				
				while $c > 0
					$char = ToChar($c)
					if $System.Char.IsNumber($char) Or $char = "."
						$length = $builder.Append($char)
						$length = $state.Reader.Read
						$c = $state.Reader.Peek
					else
						break
					endif
				loop
				
				$scanner_read = {
									Token = $tokens.Number,
									Value = $builder.ToString
								}
			case $System.Char.IsLetter($char)
				$scanner_read = {
									Token = $tokens.Var,
									Value = $char
								}
			case $char = "+"
				$scanner_read = {
									Token = $tokens.Plus,
									Value = $char
								}
			case $char = "-"
				$scanner_read = {
									Token = $tokens.Min,
									Value = $char
								}
			case $char = "*"
				$scanner_read = {
									Token = $tokens.Star,
									Value = $char
								}
			case $char = "/"
				$scanner_read = {
									Token = $tokens.Div,
									Value = $char
								}
			case $char = "("
				$scanner_read = {
									Token = $tokens.LeftPara,
									Value = $char
								}			
			case $char = ")"
				$scanner_read = {
									Token = $tokens.RightPara,
									Value = $char
								}			
		endselect		
	
		if $scanner_read = nothing
			throw 'Unsupported token'
		endif
		
		break
	loop
endfunction

;peeks token from scanner context
function scanner_peek($state)
	if $state.PeekToken = nothing
		$state.PeekToken = scanner_read($state)
	endif
	
	$scanner_peek = $state.PeekToken
endfunction

;parses expression
function parser_parseExpression($scanner)
	$parser_parseExpression = parser_parseMinPlus($scanner)
endfunction

;parses final expression (atom/variable/parenthesis)
function parser_parseFinal($scanner)
	dim $token = scanner_peek($scanner)
	dim $swallow
	
	select
		case $token.token = $tokens.Number Or $token.token = $tokens.Var
			$parser_parseFinal = {
									Token = $token,
									Left=nothing,
									Right=nothing
								}
			$swallow = scanner_read($scanner)
		case $token.token = $tokens.LeftPara
			$swallow = scanner_read($scanner)
			
			$parser_parseFinal = parser_parseExpression($scanner)
			
			$swallow = scanner_read($scanner)
	endselect
endfunction

;parses multiplication and division
function parser_parseMulDiv($scanner)
	dim $left = parser_parseFinal($scanner)
	dim $swallow
	dim $token = scanner_peek($scanner)
	
	while $token <> nothing and 
				( $token.token = $tokens.Star or $token.token = $tokens.Div )
	
		$swallow = scanner_read($scanner)
		
		dim $expr = {
						Token = $token,
						Left = $left,
						Right = parser_parseFinal($scanner)
					}
					
		$left = $expr
		
		$token = scanner_peek($scanner)	
	loop
	
	$parser_parseMulDiv = $left
endfunction

;parses addition or subtraction
function parser_parseMinPlus($scanner)
	dim $left = parser_parseMulDiv($scanner)
	dim $swallow
	
	dim $token = scanner_peek($scanner)
	
	while $token <> nothing and 
				( $token.token = $tokens.Plus or $token.token = $tokens.Min )
		
		$swallow = scanner_read($scanner)
		
		dim $expr = {
						Token = $token,
						Left = $left,
						Right = parser_parseMulDiv($scanner)
					}
					
		$left = $expr
		
		$token = scanner_peek($scanner)				
	loop
	
	$parser_parseMinPlus = $left
endfunction

;prints expression tree
function parser_print($expr, $ident)
	for $i = 1 to $ident
		" "
	next 
	
	$expr.token.value ?
	
	if $expr.left <> nothing
		parser_print($expr.left, $ident+1)
	endif
	
	if $expr.right <> nothing
		parser_print($expr.right, $ident+1)
	endif	
endfunction

;evaluate expression tree
function evaluator_eval($expr, optional $variables)
	dim $left, $right
	
	select
		case $expr.token.token = $tokens.Plus
			$left = evaluator_eval($expr.left, $variables)
			$right = evaluator_eval($expr.right, $variables)
			$evaluator_eval = $left + $right
		case $expr.token.token = $tokens.Min
			$left = evaluator_eval($expr.left, $variables)
			$right = evaluator_eval($expr.right, $variables)
			$evaluator_eval = $left - $right
		case $expr.token.token = $tokens.Star
			$left = evaluator_eval($expr.left, $variables)
			$right = evaluator_eval($expr.right, $variables)
			$evaluator_eval = $left * $right
		case $expr.token.token = $tokens.Div
			$left = evaluator_eval($expr.left, $variables)
			$right = evaluator_eval($expr.right, $variables)
			$evaluator_eval = $left / $right
		case $expr.token.token = $tokens.number
			$evaluator_eval = $System.Convert.ToDouble($expr.token.value, $System.Globalization.NumberFormatInfo() With { NumberDecimalSeparator = "." })
		case $expr.token.token = $tokens.var
			if not $variables
				throw 'Variable referenced but not defined'
			endif
			$evaluator_eval = $System.Convert.ToDouble($variables[$expr.token.value])
	endselect
	
endfunction

;"1+10 * (1+2)"

"Enter an expression. Only multiplication, addition, subtraction and division is supported. Parenthesis can be used." ?
"Example: 1+10 * (1+2)" ?
"Type exit to quit" ?

dim $input

gets $input

while $input <> "exit"
	dim $scannerState = scanner_create($input)
	dim $expr = parser_parseExpression($scannerState)
	"Result: " evaluator_eval($expr, nothing) ?
	"Tree: " ? 
	parser_print($expr, 0)
	gets $input
loop