Create a program which parses and evaluates arithmetic expressions.

Requirements

 An abstract-syntax tree (AST) for the expression must be created from parsing the input. 
 The AST must be used in evaluation, also, so the input may not be directly evaluated (e.g. by calling eval or a similar language feature.) 
 The expression will be a string or list of symbols like "(1+3)*7". 
 The four symbols + - * / must be supported as binary operators with conventional precedence rules. 
 Precedence-control parentheses must also be supported.


Note

For those who don't remember, mathematical precedence is as follows:

 Parentheses
 Multiplication/Division (left to right)
 Addition/Subtraction (left to right)


C.f
 
 24 game Player.
 Parsing/RPN calculator algorithm.
 Parsing/RPN to infix conversion.


10 PRINT "Use integer numbers and signs"'"+ - * / ( )"''
20 LET s$="": REM last symbol
30 LET pc=0: REM parenthesis counter
40 LET i$="1+2*(3+(4*5+6*7*8)-9)/10"
50 PRINT "Input = ";i$
60 FOR n=1 TO LEN i$
70 LET c$=i$(n)
80 IF c$>="0" AND c$<="9" THEN GO SUB 170: GO TO 130
90 IF c$="+" OR c$="-" THEN GO SUB 200: GO TO 130
100 IF c$="*" OR c$="/" THEN GO SUB 200: GO TO 130
110 IF c$="(" OR c$=")" THEN GO SUB 230: GO TO 130
120 GO TO 300
130 NEXT n
140 IF pc>0 THEN PRINT FLASH 1;"Parentheses not paired.": BEEP 1,-25: STOP 
150 PRINT "Result = ";VAL i$
160 STOP 
170 IF s$=")" THEN GO TO 300
180 LET s$=c$
190 RETURN 
200 IF (NOT (s$>="0" AND s$<="9")) AND s$<>")" THEN GO TO 300
210 LET s$=c$
220 RETURN 
230 IF c$="(" AND ((s$>="0" AND s$<="9") OR s$=")") THEN GO TO 300
240 IF c$=")" AND ((NOT (s$>="0" AND s$<="9")) OR s$="(") THEN GO TO 300
250 LET s$=c$
260 IF c$="(" THEN LET pc=pc+1: RETURN 
270 LET pc=pc-1
280 IF pc<0 THEN GO TO 300
290 RETURN 
300 PRINT FLASH 1;"Invalid symbol ";c$;" detected in pos ";n: BEEP 1,-25
310 STOP 
 