how to make an expression parser in c#

yazz · 2014-01-14 07:06:41

hi,i am recently working on expression parsing.and now i have made a parser that can interpret expression of single digit.

1+5*4*(7-3)

but can you give me some suggestions so that i can parse expression of numbers more than a digit.i don't know where to start over.
how ever i figured out the overall algorithm

receive the expression
tokenize them //this is where my problem rose :(
evaluate them 
output the evaluated

this may not look like an algorithm.it is kind of outline. but i managed to do all others except that i can't figure out what is the logic behind tokenizing .any help would be highly appreciated.
am i missing some details...should i give more?should i give my source code?

Last edited by yazz (2014-01-14 07:08:03)

bobbym · 2014-01-14 15:10:05

Hi;

I thought tokenizing is done for keywords. Also, the whole thing is sometimes done in RPN or at least it used to be.

yazz · 2014-01-14 15:41:00

i didn't know that.my reference book told to do.the expression parser provided in that book also parses functions.this may be the reason why they tokenize them..and also my web searchs say that converting

34.7+86

into rpn also requires tokenizing them because each string literal is not always a token in these cases ..or do you have any other idea converting intimo rpn..i know what is rpn but implementing it is little bit hard for me..

Last edited by yazz (2014-01-14 15:46:33)

bobbym · 2014-01-14 15:53:29

RPN or Reverse Polish Notation is a way to parse arithmetic. If I can remember it works something like this.

1,2 + would mean take the top 2 of the stack and add them and put it back on the stack.

So 1, 2 + would become 3,1,2

It was originally used in the old time calculators because it is supposed to make parsing simpler to do.

The first languages were BASIC on microcomputers, now called desktops, laptops etc. Tokenizing was used to make code faster and shorter. For instance:

Goto 1200 is a command in BASIC then says jump to line 1200. The Goto would be tokenized by being given an a one byte value such as 210. In ASCII this takes one byte instead of 4 for the word Goto.

In your case it does not appear necessary. Is it required for the question?

yazz · 2014-01-14 16:08:26

thank you..and a little correction.. 1 2 + will become 3 after evaluating .because 1 and 2 will be popped of from the stack.

yazz · 2014-01-14 16:12:05

and i will post my questions again when i am stuck.

bobbym · 2014-01-14 16:14:10

Thanks, it has been a long time since I ever used RPN.

You understand the stack which is a low level assembly language construct so take a look at BillK's comments over here.

http://stackoverflow.com/questions/4589 … it-in-java

yazz · 2014-01-14 16:21:09

thank you.and another thing.i know to use nodes but don't know its practical implementation.shame on myself.i also can't fins any goodonline tutorials on it.so can you help me

Last edited by yazz (2014-01-14 16:34:12)

bobbym · 2014-01-14 16:24:44

Hi;

I did not do much.

They mention this too which might help.

http://en.wikipedia.org/wiki/Shunting-yard_algorithm

yazz · 2014-01-14 16:35:34

thank you but i already know that and also implemented it.and sorry that i havn't mentioned that i know it in my algorithm.but you are really great

Last edited by yazz (2014-01-14 16:40:30)

gAr · 2014-01-14 16:47:49

Hi yazz,

You want to stick to C# only?

If your goal is to evaluate an expression, you may try Lex and Yacc and avoid worrying about tokenizing, parsing etc.

bobbym · 2014-01-14 16:50:03

Hi;

I once played with a strict left to right parser. Of course the user would have to enter the expression in the correct order.

yazz · 2014-01-14 17:38:01

you
may try Lex and Yacc and avoid worrying about
tokenizing, parsing etc.

yeah i've tried that before but it is more advanced or not meant for my goal.my goal is to learn c c++ c# and java as deep as possible...and if i were asked to build a parser with out those lex and yacc's in my future college studies i should not struggle there.and also it provides fum time on learning those things.and i am now self educative. and one more thing what are all other things i should know to become a programmer.am i clear in my question.

Last edited by yazz (2014-01-14 17:49:09)

gAr · 2014-01-14 17:58:02

Okay.
In that case, read about finite automata (DFA, NFA), regular expressions, various data structures etc. Try to make use of it as you read.
If your goal is programming, I'd like to suggest you to use any linux distribution, as it supports some programming languages out of the box.

yazz · 2014-01-14 18:01:09

linux distrib?ok i wanna rise another question..
thank you

gAr · 2014-01-14 18:16:42

Yes, and as a good programmer, you must ensure that it can be used in any OS.

C# is developed by m$. Though there is the mono project, the standards for c# is at m$'s mercy. All may not work well in other OSes.

yazz · 2014-01-14 19:15:09

so java would be my choice right now..

gAr · 2014-01-14 19:40:44

Not at all.
I did not say to stick to a language. You can write code in any language (python, C, perl, ruby etc.), just don't use platform specific APIs.

yazz · 2014-01-14 19:46:23

ok thank you...now i am gonna start my coding..in which language?

Last edited by yazz (2014-01-14 19:47:42)

gAr · 2014-01-14 20:05:43

See examples in rosetta code and decide.

yazz · 2014-01-14 20:10:11

great..

gAr · 2014-01-14 20:16:10

If you can write a pseudo-code unambiguously, you may pick any language of your choice to write the code.

yazz · 2014-01-14 21:30:48

right ..i am picking c++..bcoz if i manage to do it in c++,then i can make it again in other languages in no time.it also has performance advantage

gAr · 2014-01-14 22:00:49

The executable will run quickly, but coding time will be more.
Initially, a scripting language like python may work better for you (among the languages I have used), since it doesn't require you to mention the data type when defining a variable or care about issues like integer overflow etc.

If you are thinking of system programming, then it's necessary that you learn C/C++ or even assembly.

yazz · 2014-01-14 22:04:19

but i don't know python..soon i will

Math Is Fun Forum

#1 2014-01-14 07:06:41

how to make an expression parser in c#

#2 2014-01-14 15:10:05

Re: how to make an expression parser in c#

#3 2014-01-14 15:41:00

Re: how to make an expression parser in c#

#4 2014-01-14 15:53:29

Re: how to make an expression parser in c#

#5 2014-01-14 16:08:26

Re: how to make an expression parser in c#

#6 2014-01-14 16:12:05

Re: how to make an expression parser in c#

#7 2014-01-14 16:14:10

Re: how to make an expression parser in c#

#8 2014-01-14 16:21:09

Re: how to make an expression parser in c#

#9 2014-01-14 16:24:44

Re: how to make an expression parser in c#

#10 2014-01-14 16:35:34

Re: how to make an expression parser in c#

#11 2014-01-14 16:47:49

Re: how to make an expression parser in c#

#12 2014-01-14 16:50:03

Re: how to make an expression parser in c#

#13 2014-01-14 17:38:01

Re: how to make an expression parser in c#

#14 2014-01-14 17:58:02

Re: how to make an expression parser in c#

#15 2014-01-14 18:01:09

Re: how to make an expression parser in c#

#16 2014-01-14 18:16:42

Re: how to make an expression parser in c#

#17 2014-01-14 19:15:09

Re: how to make an expression parser in c#

#18 2014-01-14 19:40:44

Re: how to make an expression parser in c#

#19 2014-01-14 19:46:23

Re: how to make an expression parser in c#

#20 2014-01-14 20:05:43

Re: how to make an expression parser in c#

#21 2014-01-14 20:10:11

Re: how to make an expression parser in c#

#22 2014-01-14 20:16:10

Re: how to make an expression parser in c#

#23 2014-01-14 21:30:48

Re: how to make an expression parser in c#

#24 2014-01-14 22:00:49

Re: how to make an expression parser in c#

#25 2014-01-14 22:04:19

Re: how to make an expression parser in c#

Board footer