Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

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

yazz
Member
Registered: 2014-01-14
Posts: 412

how to make an expression parser in c#

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)


Knowledge is knowing that a tomato is a
fruit, but Wisdom is knowing not to put it in a fruit salad tongue.

Offline

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,379

Re: how to make an expression parser in c#

Hi;

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


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Online

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

yazz
Member
Registered: 2014-01-14
Posts: 412

Re: how to make an expression parser in c#

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 yikes 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)


Knowledge is knowing that a tomato is a
fruit, but Wisdom is knowing not to put it in a fruit salad tongue.

Offline

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,379

Re: how to make an expression parser in c#

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?


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Online

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

yazz
Member
Registered: 2014-01-14
Posts: 412

Re: how to make an expression parser in c#

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


Knowledge is knowing that a tomato is a
fruit, but Wisdom is knowing not to put it in a fruit salad tongue.

Offline

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

yazz
Member
Registered: 2014-01-14
Posts: 412

Re: how to make an expression parser in c#

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


Knowledge is knowing that a tomato is a
fruit, but Wisdom is knowing not to put it in a fruit salad tongue.

Offline

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,379

Re: how to make an expression parser in c#

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


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Online

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

yazz
Member
Registered: 2014-01-14
Posts: 412

Re: how to make an expression parser in c#

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)


Knowledge is knowing that a tomato is a
fruit, but Wisdom is knowing not to put it in a fruit salad tongue.

Offline

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,379

Re: how to make an expression parser in c#

Hi;

I did not do much.

They mention this too which might help.

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


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Online

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

yazz
Member
Registered: 2014-01-14
Posts: 412

Re: how to make an expression parser in c#

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)


Knowledge is knowing that a tomato is a
fruit, but Wisdom is knowing not to put it in a fruit salad tongue.

Offline

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

gAr
Member
Registered: 2011-01-09
Posts: 3,479

Re: how to make an expression parser in c#

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.


"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,379

Re: how to make an expression parser in c#

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.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Online

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

yazz
Member
Registered: 2014-01-14
Posts: 412

Re: how to make an expression parser in c#

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)


Knowledge is knowing that a tomato is a
fruit, but Wisdom is knowing not to put it in a fruit salad tongue.

Offline

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

gAr
Member
Registered: 2011-01-09
Posts: 3,479

Re: how to make an expression parser in c#

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.


"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

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

yazz
Member
Registered: 2014-01-14
Posts: 412

Re: how to make an expression parser in c#

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


Knowledge is knowing that a tomato is a
fruit, but Wisdom is knowing not to put it in a fruit salad tongue.

Offline

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

gAr
Member
Registered: 2011-01-09
Posts: 3,479

Re: how to make an expression parser in c#

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.


"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

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

yazz
Member
Registered: 2014-01-14
Posts: 412

Re: how to make an expression parser in c#

so java would be my choice right now..


Knowledge is knowing that a tomato is a
fruit, but Wisdom is knowing not to put it in a fruit salad tongue.

Offline

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

gAr
Member
Registered: 2011-01-09
Posts: 3,479

Re: how to make an expression parser in c#

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.


"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

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

yazz
Member
Registered: 2014-01-14
Posts: 412

Re: how to make an expression parser in c#

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

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


Knowledge is knowing that a tomato is a
fruit, but Wisdom is knowing not to put it in a fruit salad tongue.

Offline

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

gAr
Member
Registered: 2011-01-09
Posts: 3,479

Re: how to make an expression parser in c#

See examples in rosetta code and decide.


"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

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

yazz
Member
Registered: 2014-01-14
Posts: 412

Re: how to make an expression parser in c#

great..


Knowledge is knowing that a tomato is a
fruit, but Wisdom is knowing not to put it in a fruit salad tongue.

Offline

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

gAr
Member
Registered: 2011-01-09
Posts: 3,479

Re: how to make an expression parser in c#

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


"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

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

yazz
Member
Registered: 2014-01-14
Posts: 412

Re: how to make an expression parser in c#

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


Knowledge is knowing that a tomato is a
fruit, but Wisdom is knowing not to put it in a fruit salad tongue.

Offline

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

gAr
Member
Registered: 2011-01-09
Posts: 3,479

Re: how to make an expression parser in c#

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.


"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

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

yazz
Member
Registered: 2014-01-14
Posts: 412

Re: how to make an expression parser in c#

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


Knowledge is knowing that a tomato is a
fruit, but Wisdom is knowing not to put it in a fruit salad tongue.

Offline

Board footer

Powered by FluxBB