One for mark..
BlitzMax Forums/BlitzMax Programming/One for mark..
| ||
Or anyone else who knows how to parse expressions, basically I'm writing a script language in bmax, Basic# if you like, like C# with the syntax of basic. It's going fine, it's all done parsed and converted into opcodes, but when it comes to running the code, I can't do an expression parser with oepration precendence. The current one posted below processes expressions but it does so in order. Here's the whole code. Here's the expression part it's self, Method ExecExpression( ep:expression.ep,index Var) nnum = ep.op[index].van Select ep.op[index].toke Case t_add,t_minus lop=ep.op[index].toke Case t_times lop=t_Times Case t_devide lop=t_devide Case T_numeric Select lop Case t_add lnum:+nnum Case t_minus lnum:-nnum Case t_times lnum:*nnum Case t_devide lnum:/nnum Default lnum = ep.op[index].van End Select End Select index+1 execexpression( ep,index ) End Method It simply fills a double variable or operates on it based on the last active opeator. Each expression contained within paranatheses(spellcheck, stat) are already grouped off by the parser(for no real reason other than to make it easier to process fast at run time) so (2+2*(4+4)) will be grouped off into two seperate expressions. The idea being I can process each individual expression, then create a simplified dynamic expression consisting of their whole values and then run that through the expression processor. Here's a test prog. Class Main int i function void program() i = 2*2 end function End Class Strict 'DaVinchi2D ' Import "tokens.bmx" Global toke_id=0 Type deli Field id Global cur:TList Field tag Function deliTag( deli$,ntag ) Local del = deli[0] For Local d:deli = EachIn cur If d.id = del d.tag=ntag End If Next End Function Function setcurrent( d:TList ) cur = d End Function Function isDel( in ) For Local de:Deli = EachIn cur If de.id = in Return True Next Return False End Function Function hastag( in ) For Local de:Deli = EachIn cur If de.id = in If de.tag<>0 Return True End If Next Return False End Function Function Create:Deli( word ) Local out:deli = New deli out.id = word Return out End Function Method debug() Print "Delimiter Debug spool:" Print "Actual id:"+id Print "Textural referece "+Chr(id) End Method Function CreateDelis:TList( words$ ) Local dli:TList = CreateList() Local wl = Len(words) For Local j=1 To wl Local d:Deli = deli.create( words[j] ) dli.addlast( d ) Next cur = dli Return dli End Function Function debugList( in:TList ) For Local v:Object = EachIn in Local d:Deli = Deli(v) d.debug() Next End Function End Type Type tokens Field tokes:TList Field toke:Object[] Method set( tok:TList ) tokes = tok toke = tok.toarray() End Method Function create:Tokens() Return New tokens End Function Method New() tokes = CreateList() End Method Method add( itoke:Token ) tokes.addlast( itoke ) toke = tokes.toarray() End Method Method debug() For Local t:Token = EachIn tokes Print t.id Next End Method End Type Type token Field id$ Function Create:Token( toke$ ) Local out:token = New token out.id = toke Return out End Function Function CreateTokens:TList( tokes$ ) Local out:TList = CreateList() Local tc = Len(tokes) For Local j=1 To tc Local nt:token = token.create( tokes[j] ) out.addlast( nt ) nt.debug() Next 'Print "Approx " + CountList(out)+"Tokens were defined' Return out End Function Method debug() Print "Token symbolic info" Print id End Method End Type Type tokenizer Function create:tokenizer() Return New tokenizer End Function Method Tokenize:Tokens( text:String ) text = " "+text+" " Local tk:Tokens = tokens.create() Local lvc,fvc lvc=-1 fvc=-1 Local tl= Len(text) Local snc=0,igdot=0 For Local j=0 To tl-1 Local li = text[j] If li = 39 If snc=0 fvc=j+1 snc=1 Else lvc=j-1 snc=0 EndIf EndIf If li>47 And li<58 igdot = True End If Local skpdel=0 If snc=0 If deli.isdel( li ) If igdot = True If li = 46 skpdel=True End If EndIf If Not skpdel If lvc<>fvc And fvc<>-1 If lvc<fvc lvc=fvc Local tst$ = text[fvc..lvc+1] ' Print "Token:"+tst tk.add( token.create( tst ) ) fvc=-1 lvc=-1 EndIf If deli.hastag( li ) tk.add( token.create( Chr(li) ) ) Print "deli "+li+" Had a tag" EndIf igdot=False End If Else If fvc=-1 fvc=j Else lvc=j EndIf EndIf EndIf Next Return tk End Method End Type Type scope Method New() vpool = CreateList() scope.scopes.addlast( Self ) tokes = CreateList() funcs = CreateList() code = CreateList() classes = CreateList() End Method Function debug() For Local sc:scope = EachIn scope.scopes Print "Scope Variables:" For Local va:Varn = EachIn sc.vpool Print "Variable :"+va.name+" Value:"+varValue( va ) Next Print "Scope has "+sc.code.count()+" Lines of code" Next End Function Method clone:Scope() Local out:scope = New scope For Local vn:Varn = EachIn vpool out.vpool.addlast( vn ) Next Return out End Method Method copyvars( in:scope ) For Local va:Varn = EachIn in.vpool vpool.addlast( va ) Next End Method Method findvar:varn( nam:String ) For Local vn:varn = EachIn vpool If vn.name = nam Return vn End If Next End Method Method addvar( Va:Varn ) If va = Null Print "Cannot add null variable." Return End If For Local vn:varn = EachIn vpool If vn.name.tolower() = va.name.tolower() Throw "Variable |"+va.name+"| already exists within current scope" End If Next vpool.addlast( va ) End Method Field tokes:TList Field vpool:TList Field own:scope Global scopes:TList Field funcs:TList Method addfunc( fun:func ) funcs.addlast( fun:Func ) End Method Field classes:TList Method addclass( clas:Class ) classes.addlast( clas ) End Method Field code:TList End Type scope.scopes=CreateList() Type varn Abstract Field name$ Field val End Type Type vari Extends varn Field val% End Type Type varf Extends varn Field val# End Type Type vard Extends varn Field Val! End Type Type vars Extends varn Field val$ End Type Type varia Extends varn Field val%[] End Type Type varfa Extends varn Field val#[] End Type Function varValue:String( va:Varn ) If vari(va)<>Null Local vai:Vari = vari(va) Return vai.val End If If varf(va)<>Null Local vaf:varf = varf(va) Return vaf.val End If If vard(va)<>Null Local vad:vard = vard(va) Return vad.val End If If vars(va)<>Null Local vas:vars = vars(va) Return vas.val End If End Function Type class Extends varn Method New() code = CreateList() funcs= CreateList() class.classes.addlast( Self ) End Method Method findfunc:Func( nam:String ) For Local fun:func = EachIn funcs If fun.name = nam Return fun Next Return Null End Method Function find:Class( nam:String ) For Local cla:class = EachIn class.classes If cla.name = nam Return cla End If Next Return Null End Function Field classto$ Field scop:Scope Field code:TList Field funcs:TList Field be,fi Global classes:TList Field real:Class End Type class.classes = CreateList() Type func Method New() in = CreateList() End Method Field name:String Field scop:Scope Field in:TList Field be,fi Field ops:opline[5000],opl Method addOp( op:Opline ) ops[opl] = op opl:+1 End Method Field toke:Tokens[5000],toc Method AddTokeLine( ntoke:tokens ) toke[ toc ] = ntoke toc:+1 End Method End Type Type Cpu Field mem:Byte Ptr 'global memory heap Field stack:Byte Ptr 'local dynamic stack Field msize,ssize Function Create:Cpu( memsize = 32,stacksize =1 ) Local out:Cpu = New cpu out.mem = MemAlloc( memsize*1024 ) out.stack = MemAlloc( memsize*1024 ) out.msize = memsize out.ssize =stacksize Return out End Function Method Delete() MemFree mem,msize*1024 MemFree stack,ssize*1024 End Method Method run:varn( main:Class ) Local pf:Func = main.findFunc("program") If pf = Null Print "Program function not defined or illegally defined." End End If Print "Found main func." ato=Null runFunc( pf ) End Method Method runfunc( in:func ) For Local j=0 Until in.opl Local op:opline = in.ops[j] Local index=0 ExecOp( op,index ) Next End Method Method ExecOp( op:Opline,index Var ) If index=>op.opl Return If op.op[index].ep<>Null Local eindex=0 ExecExpression( op.op[index].ep,eindex ) Print "Expression result:"+lnum End If Select op.op[index].toke Case t_var If index+1<op.opl Select op.op[index+1].toke Case t_assign index:+2 ExecOp(op,index) Return End Select End If Case t_class Select op.op[index+1].toke Case t_entry index:+2 ExecOp(op,index) Return End Select Case t_funccall index:+1 ExecOp(op,index) Return End Select End Method Local ostack[255],oc Local val![255],vc Local cnum!,lnum!,lop Method ExecExpression( ep:expression.ep,index Var) nnum = ep.op[index].van Select ep.op[index].toke Case t_add,t_minus lop=ep.op[index].toke Case t_times lop=t_Times Case t_devide lop=t_devide Case T_numeric Select lop Case t_add lnum:+nnum Case t_minus lnum:-nnum Case t_times lnum:*nnum Case t_devide lnum:/nnum Default lnum = ep.op[index].van End Select End Select index+1 execexpression( ep,index ) End Method Field num![255],nv Field opv[255],ov Field anum!,eop Method procExp( op:opline,ind Var ) End Method Field expnum! Field ato:varn Method procSeq( ops:opline,ind Var ) Local op:Opcode = ops.op[ind] Select op.toke Case t_var End Select End Method End Type Type expression Field op:opcode[255],opl Method addToke( opc:opcode) op[opl]=opc opl:+1 End Method Field lval!,lvas$ End Type Type opline Field op:opcode[255],opl Field ep:expression[255],ec,ce Method newexp:expression() ep[ec] = New expression ec:+1 Return ep[ec-1] End Method Method addExp(opc:opcode) ep[ce].addtoke( opc ) End Method Method backExp() ce=ce-1 If ce<-1 Print "Attempt to write to expression that does not exist." End End If End Method End Type Type opcode Field toke Field ep:expression Field Vo:varn Field vas:String Field van:Double Method debug() Print "Toke Debug:"+toke Print "VAS:"+vas+" VAN:"+String(van) End Method End Type Type Parser Field toker:Tokenizer Field prog:TList Method New() toker = New tokenizer prog = CreateList() End Method Method Debug() For Local tk:tokens =EachIn prog For Local toke:Token = EachIn tk.tokes Print "Token |"+toke.id+"|" Next Next End Method Method LoadApp( file:String ) Local fi = ReadFile(File) If fi =0 Print file+" not found." End If While Not Eof(fi) prog.addlast( toker.tokenize( ReadLine(fi) ) ) Wend CloseFile fi Print "App has "+CountList( prog)+" lines of code" End Method Method parse:class() Local gMode=0 Local mainscope:Scope = New scope Local cscope:Scope = mainscope Local cclass:Class Local lscope:Scope Local cfunc:func Local l_gmode Local fs = WriteFile( "test.cpp" ) Local tokel=0 For Local tk:Tokens = EachIn prog Local toka:Object[] = tk.tokes.toarray() If toka.length=0 Continue Local toke:token[ toka.length ] For Local j=0 To toka.length-1 toke[j] = token( toka[j] ) toke[j].id = toke[j].id.tolower() Next Local isCode=True Select toke[0].id Case "class" Local className:String = toke[1].id Print "New class "+Classname l_gmode = gmode gmode = g_inclass cclass = New class cclass.scop = New scope cscope = cclass.scop cscope.own = mainscope cclass.name = classname iscode=False cclass.be = tokel Case "function" Print "New Function" Local retType:String = toke[1].id Local funcname:String = toke[2].id Print "Function name:"+funcname+" Return type:"+rettype lscope = cscope Local fun:func = New func cscope.addfunc( fun ) If gmode=g_inclass fun.scop = cscope.clone() Else fun.scop = mainscope.clone() EndIf If cclass<>Null cclass.funcs.addlast( fun ) End If fun.name = funcname fun.scop.own = lscope cscope = fun.scop l_gmode = gmode gmode = g_infunc 'GenVars( toke,4,fun.scop,fun.in ) iscode=False fun.be=tokel cfunc=fun Case "end" If toke.length>1 Select toke[1].id Case "class" If gmode<>g_inclass Throw "End class without class definition" End If gmode = l_gmode cclass.fi=tokel cclass = Null cscope = mainscope Print "End of class definition" iscode=False Case "function" If gmode<>g_infunc Print "End function without function definition" End If cfunc.fi = tokel cfunc=Null gmode = l_gmode cscope = lscope iscode=False End Select End If 'Case "int","float","double","string" ' Print "variable type:"+toke[0].id ' For Local j=1 Until toke.length ' Local va:Varn = genvar( toke[0].id,toke[j].id ) ' cscope.addvar(va) ' Next ' iscode=False End Select ' If iscode ' cscope.code.addlast( tk ) 'EndIf If cfunc<>Null cfunc.addtokeline( tk ) End If tokel:+1 Next Local pcode:Object[] = prog.toarray() For Local Cla:Class = EachIn class.classes cscope = cla.scop For Local j=cla.be To cla.fi Local tk:Tokens = tokens( pcode[j] ) Local toka:Object[] = tk.tokes.toarray() If toka.length=0 Continue Local toke:token[ toka.length ] For Local j=0 To toka.length-1 toke[j] = token( toka[j] ) toke[j].id = toke[j].id.tolower() Next Select toke[0].id Case "int","float","double","string" Print "variable type:"+toke[0].id For Local j=1 Until toke.length Print "Var Name:"+toke[j].id Local va:Varn = genvar( toke[0].id,toke[j].id ) cscope.addvar(va) Next Case "function" Local fun:func = cla.findfunc( toke[2].id ) If fun = Null Print "Syntax error. Function "+toke[2].id+" illegally defined." End End If cfunc = fun cscope = fun.scop GenVars( toke,4,fun.scop,fun.in ) ' fun.be = j Case "end" If toke.length>1 If toke[1].id="function" cscope = cla.scop ' cfunc.fi = j End If End If Default If toke.length>1 Local vcl:Class = class.find( toke[0].id ) If vcl<>Null Local vn:Varn= genvar( toke[0].id,toke[1].id ) cscope.addvar( vn ) End If End If End Select Next Next For Local cla:Class = EachIn class.classes For Local fun:func = EachIn cla.funcs fun.scop.copyvars( cla.scop ) Print "Func name:"+fun.name Print "Start line:"+fun.be Print "Fin line:"+fun.fi For Local j=1 To fun.toc-1 Local tk:Tokens = fun.toke[j] 'tokens( pcode[j] ) Local toka:Object[] = tk.tokes.toarray() If toka.length=0 Continue Local toke:token[ toka.length ] For Local k=0 To toka.length-1 toke[k] = token( toka[k] ) toke[k].id = toke[k].id.tolower() Next Local ol:opline = New opline Local ade=0 For Local k=0 Until toke.length Local tokeid= tokeType( toke,k,cla,fun) Print "Token:"+tokeid Local oc:opcode = New opcode oc.toke = tokeid ol.op[ol.opl]=oc ol.opl:+1 Select tokeid Case t_var,t_class Local vn:varn = fun.scop.findvar( toke[k].id ) oc.vo = vn Case t_numeric oc.van = Double(toke[k].id) Print "Added Numeric :"+toke[k].id If Mid(toke[k].id,toke[k].id.length,1)="f" Print "Was a floating point numeric" Else If Instr(toke[k].id,".")>0 Print "Was a double" Else Print "Was a int." End If End If Case t_string oc.vas = toke[k].id End Select Next Local index=0 processExpression( ol,index) fun.addop( ol ) Next Next Next Local cla:class = class.find( "main" ) If cla = Null Print "Main class not defined or illegally defined." End End If Return cla End Method Method ProcessExpression( op:opline,index Var ) If index=>op.opl Return Select op.op[index].toke Case t_var If index+1<op.opl Select op.op[index+1].toke Case t_assign index:+2 processExpression(op,index) Return End Select End If Case t_class Select op.op[index+1].toke Case t_entry index:+2 processExpression(op,index) Return End Select Case t_funccall index:+1 processExpression(op,index) Return End Select Print "Expressin toke id:"+op.op[index].toke Select op.op[index].toke Case t_scopein Local ep:Expression = op.newexp() op.op[index].ep = ep Case t_scopeout op.backexp() Default op.addExp( op.op[index] ) op.op[index].debug() End Select index:+1 processExpression(op,index) End Method Method procop( op:opline ) Select op.op[0].toke Case t_var End Select End Method Method tokeType( toke:token[],ind Var,inclass:class,infunc:func) Print "Token for:"+toke[ind].id Select toke[ind].id Case "if" Return t_if Case "(" Return t_scopeIn Case ")" Return t_scopeout Case "else" Return t_else Case "." Return t_entry Case "new" Return t_new Case "end" Select toke[ind+1].id Case "if" ind:+1 Return t_endif Case "select" ind:+1 Return t_endselect End Select Case "case" Return t_case Case "select" Return t_select Case "for" Return t_for Case "next" Return t_next Case "step" Return t_step Case "+" Return t_add Case "-" Return t_sub Case "/" Return t_devide Case "*" Return t_times Case "=" Return t_assign End Select Local cla:class = class.find( toke[ind].id ) If cla<>Null Return t_class End If Local fun:func = inclass.findfunc( toke[ind].id ) If fun<>Null Return t_funccall End If If infunc.scop = Null Else Local va:Varn = infunc.scop.findvar( toke[ind].id ) If va<>Null Return t_var End If End If If toke[ind].id[0]>47 And toke[ind].id[0]<58 Return t_numeric End If Return t_funccall End Method Method genVars( toke:Token[],from,scop:scope,tl:TList ) For Local j=from Until toke.length Step 2 Select toke[j].id Case "(" Case ")" Return Default Print "Toke ID:"+toke[j].id Local vn:Varn = genvar( toke[j].id,toke[j+1].id ) If vn <>Null tl.addlast( vn ) scop.addvar( vn ) End If End Select Next End Method End Type Function genVar:Varn( typ:String,name:String) Select typ Case "int" Local out:vari = New vari out.name=name Return out Case "float" Local out:varf = New varf out.name=name Return out Case "double" Local out:vard = New vard out.name=name Return out Case "string" Local out:vars = New vars out.name=name Return out Default Local cla:class = class.find(typ) If cla<>Null Local out:class = New class out.name = name out.real = cla Return out Else Print "Unknown variable type:"+typ End End If End Select End Function Function err(cond,error$,resp=1) If cond=True Return Print error Select resp Case 1 End End Select End Function Const g_main=1,g_inclass=2,g_infunc=3,g_intemplate=5 Const Scope_Entry=1,Scope_Exit=2 Const Assign = 3,Minus=4,Plus=5,Times=7,Devide=8 Const classentry=9 Const delimiters:String = "{}[]';;!@#$%^&*()_+=-/.,?{><\|<> ` " Global maindel:TList = deli.createdelis( delimiters ) deli.delitag( "(",Scope_Entry ) deli.delitag( ")",Scope_Exit ) deli.delitag( "=",Assign ) deli.delitag( "-",Minus) deli.delitag( "+",Plus) deli.delitag( "*",Times) deli.delitag( "/",Devide) deli.delitag( ".",ClassEntry) Local tp:Parser = New parser tp.loadapp("test.txt") Local prog:Class Print "Debug ------" Try prog = tp.parse() Catch s$ Print s End End Try Local cp:Cpu = cpu.create() cp.run( prog ) End |
| ||
Some example code would be great. Something that works on the assumption each element in the expression is a unique object, like in my code. I.e fill out this template [code] type obj field val,typ end type local o1,o2,o3 o1:obj = createValue("1") o2:obj = CreateOperator("+") o3:obj = createValue("5") I.e i'm not looking for something that parses or tokenizes the expression, that's already done. |
| ||
'tokes Const t_if=1,t_else=2,t_endif=3 Const t_select=4,t_case=5,t_endselect=6 Const t_funccall=7,t_assign=8,t_var=9,t_class=10 Const t_constant=11,t_string=12,t_numeric=13 Const t_add=14,t_sub=15,t_times=16,t_devide=17 Const t_is=18,t_for=19,t_next=20,t_step=21,t_entry=22,t_new=23 Const t_scopein=24,t_scopeout=25 forgot the tokens import. |
| ||
'tokes Const t_if=1,t_else=2,t_endif=3 Const t_select=4,t_case=5,t_endselect=6 Const t_funccall=7,t_assign=8,t_var=9,t_class=10 Const t_constant=11,t_string=12,t_numeric=13 Const t_add=14,t_sub=15,t_times=16,t_devide=17 Const t_is=18,t_for=19,t_next=20,t_step=21,t_entry=22,t_new=23 Const t_scopein=24,t_scopeout=25 forgot the tokens import. |
| ||
Try Googling "Operator Precedence Parsing". It is good just for parsing expressions, but not very good for parsing entire languages, although it is possible. |
| ||
A great way to go about it is writing a Post Fix to Reverse Polish Notation convertor, from there you can simply write a 'stack machine' based operation. Infact I wrote one for blitz3d a while ago, should be in the code archives. Click on my name. :) (btw, hey antony, long time no talk XD) http://www.blitzbasic.com/codearcs/codearcs.php?code=926 (Pardon the old ugly code!) Oh, and also my math evaluator - http://www.blitzbasic.com/codearcs/codearcs.php?code=931 Can't remember how good it is, I'm not sure if it can do negative numbers, haha.. |
| ||
you might find some help in (the old) Crenshaws "Let's build a compiler" series.. here; http://compilers.iecc.com/crenshaw/ |
| ||
Zenith, your the second person I've seen suggest that. Could you elabrotate a bit more on what doing that would actually entail? I'm useless at understanding other people's code unless it's laden with comments and pointed out to me as if I was an idiot. Because in all probabilities, I am. Largs, thanks, already found that one and found it to be as much help as a umbrella in space. |
| ||
Yeah, I'm teh same way with code -- sorry. Basically, I dont' even know what I did, I havn't touched the code in about 2 years. :) But here's the article I looked at (other than the red dragon compiler book!) http://www.qiksearch.com/articles/cs/infix-postfix/ |
| ||
So you had no prior knowledge once you looked at that article? Cos I'm basically in the same boat, despite all the above(All coded based on Antony-Techniques (c)2005 rather than any pre-existing methods.) I found all the tutorials to be...like the jungle. Big and scary. |
| ||
If you want to learn how to write compilers use the book that Zenith mentioned, its real title is something like Compilers: Principles, Tools, and something like that by Aho Sethi and Ullman, but it is better know as "The Dragon Book" because of the dragon on its cover. Talks about everything used in compiler design from Lexical Analysis to Parsing to Bootstraping a compiler. I would like to know, did you write a specific grammar for your compiler and then work from there and translate that into BMX code, or did you just work from your head into BMX? |
| ||
I invented the grammar as it were on the fly. It's an almagmation(spell check, that.) of C# and basic though in reality so it's not like I re-invented the wheel. |
| ||
http://en.wikipedia.org/wiki/Postfix_notation#Converting_from_infix_notation When I made some scripting languages in b3d I wrote this section of a wikipedia article as no other website seemed to have a complete outline of how to parse math. |
| ||
Thanks bot. Any interest in co-writing the script engine bot or anyone with the knowledge, for a share of the profits when it goes commercial? Even if it's just working on the maths parsing problem bit. I could do with some help as tutorials just don't seem to stick. |
| ||
Been reading your site Bot, seems like the way to go but any chance you could knock up a simple conversation function example that takes tokens and converts them into rpn notion? Here's the template code so all you have to do is fill in the blanks, and i'll use this as a basis for conversation. I'll throw in a free license to this once done, it'll be a script language for bmax + a virtual machine for non blitz maxers like net framework is. type token field toke,number# end type const toke_add=1,toke_plus=2,toke_function=3,toke_sub=4,toke_devide=5 function NewToken:Token(typ,num=0) local t:token = new token t.toke = typ t.number = num return t end function 'example local tokes:Token[10] tokes[0] = new Token(toke_number,4); number token toke tokes[1] = new Token(toke_add) tokes[2] = new token(toke_number,5) tokes[3] = new token(toke_times) tokes[4] = new token(toke_number,2) function convert:token[](tokes:token[]) for local j=0 until tokes.length next end function |
| ||
I've coded a simple converter that works for very simple expressions like 4+4-2 but I still don't get it. Say you have an expression 4-2+4+4? it'll be converted to, 4244-++ How does that help me? There's no way of knowing the order of the operations. Or do I keep the value and operator stacks seperate when actually evaluating? Local op:opline = New opline op.op[0] = New opcode op.op[1] = New opcode op.op[2] = New opcode op.opl=3 op.op[0].toke=t_numeric op.op[0].van = 4 op.op[1].toke=t_add op.op[2].toke=t_numeric op.op[2].van = 8 op.debugenglish() op = conviff( op ) op.debugenglish() Function conviff:opline( op:opline ) Local opstack:opcode[255],oc Local out:opline = New opline For Local j=0 Until op.opl Select op.op[j].toke Case t_add,t_sub,t_devide,t_times opstack[oc]=op.op[j] oc:+1 Case t_numeric out.op[out.opl]=op.op[j] out.opl:+1 End Select Next For Local j=0 Until oc out.op[out.opl] = opstack[j] out.opl:+1 Next Return out End Function |
| ||
For the operation order (*/ before +-) you could handle the +- expressions as encapsulated part. So a+b*c-d would become (a+b)*(c-d) -> ab+cd-* or similar Beside that your conversion seems to be wrong, it should be: 42-4+4+ if it is meant to work as single stack (With that information you can create a parsing tree with operators in tree nodes and values in leaves, which is what you wanted to know) |
| ||
Yeah I think you can create a tree like:4-2+4+4: + / \ + 4 / \ - 4 / \ 4 2 That would be the parse tree for the infix notation 4-2+4+4. Then you just go from bottom to top to convert to RPN: Push '4' onto the stack, then '2' cause that is the bottom most leaf. Then you push '-' onto the stack cause that is the next level up. At that same level is another '4' which you push onto the stack. Then up a level is '+' and '4' and then the final level of '4'. So then your stack contains '42-4+4+' which is the RPN version of your equation. Basically you just push them onto the stack in the order you find them going from left to right and bottom to top in the parse tree. |
| ||
Bah it's still all double dutch to me. Anyone who helps me code this gets a free copy of vivid.2d.net and any other project I make in the future. I just can't do it. It's like there's some sort of dampening field obscuring the knowledge in my brain. |
| ||
Antony, Contact me via email (spammehere@...). I have code that parses math. I wrote it in Delphi, but you should be able to follow the logic of it. I can also try to explain how it works. It's easier then it looks :-) |
| ||
will do, thanks. you'll have to explain really, 'cos i've seen code examples, even simple ones wrote in blitz, but it just doesn't compute. I'm an idiot. |
| ||
You're not a complete idiot, I struggled with the same problem for almost a year or two(on and off). When you figure it out, you won't be able to express it in words; Maybe syllables, but that's about it. :) |
| ||
Thanks, although there is still the possibility that we're both complete idiots, explaining the snergy :) |