Qbasicnews.com

QbasicNews.Com => Challenges => Topic started by: Frontrunner on April 21, 2008, 10:15:33 AM



Title: Mathematical expression translator
Post by: Frontrunner on April 21, 2008, 10:15:33 AM
Hi all...

My challenge is to write a routine which will translate correctly (in all circumstances) pow functions as done in C.

The winner we judged on two things.
1) Translations must be correct
2) Efficiency

Example:
Basic
r1 = (-c + (SQR(b(x) ^ 2 - (4 * a * c)))) / (2 * a)

C
r1 = (-c + (sqrt(pow(b(x), 2) - (4 * a * c)))) / (2 * a)

Good luck!
Fronrunner


Title: Re: Mathematical expression translator
Post by: wildcard on April 21, 2008, 03:48:18 PM
Sounds like an interesting, if quite specific, challenge. Its too bad I'm busy at the moment as I have always wanted to get around to writing parsers.


Title: Re: Mathematical expression translator
Post by: Frontrunner on April 21, 2008, 04:08:58 PM
That's right, it is quite specific but a general parser would be too easy for a challenge ::)

Cheers,
Frontrunner


Title: Re: Mathematical expression translator
Post by: wildcard on April 22, 2008, 04:17:20 AM
Hopefully I can get some time to have a go, seems straight forward enough but will see.


Title: Re: Mathematical expression translator
Post by: Frontrunner on April 22, 2008, 06:57:00 AM
I am looking forward to see your contribution!

Cheers,
Frontrunner


Title: Re: Mathematical expression translator
Post by: Ralph on April 22, 2008, 09:40:28 PM
Could you please be patient with me and tell me what POW stands for?  The only meaning I have for those three letters at present is, Prisoner Of War, and, I'm sure, that is not what is intended.  :(


Title: Re: Mathematical expression translator
Post by: Frontrunner on April 23, 2008, 03:54:24 AM
Hi Ralph,

Sure I will try to explain you what POW means:

Like in qbasic there is in C a mathematical function to compute the power exponent.
In qbasic we use ^ but in C it is called POW.

I will give some more example in both C and bqasic so you can see the differences.

Example in C
  printf ("7 ^ 3 = %lf\n", pow (7,3));
  printf ("4.73 ^ 12 = %lf\n", pow (4.73,12));
  printf ("32.01 ^ 1.54 = %lf\n", pow (32.01,1.54));

Example in qbasic
  print "7 ^ 3 = ", 7 ^ 3
  print "4.73 ^ 3 = ", 4.73 ^ 12
  print "32.01 ^ 1.54 = ", 32.01 ^ 1.54

Both should output something like this:
7 ^ 3 = 343.000000
4.73 ^ 12 = 125410439.217423
32.01 ^ 1.54 = 208.036691

Please forget the C syntax you see in the example.
A correct translation (according to this challenge) should translate print 3 ^ 7 to print pow(3,7).

Now this looks easy but things start to get more complicated when translating
print (10 ^ 2) - 5 + (21 * (3 - 4 ^ 6) * 2 + 10 - 5) ^ 2 + 3 - (3 + 7) + 99
To
print pow(10,2))-5+pow((21*(3-pow(4,6))*2+10-5),2)+3-(3+7)+99)

I hope that helped a little.

Kind regards,
Frontrunner


Title: Re: Mathematical expression translator
Post by: Ralph on April 23, 2008, 03:09:47 PM
Frontrunner:

Yes, I now understand what your challenge is all about; translating a qb expression with a power expression into its equivalent code in C. 

I am not into C, so, I can not compete.  But, I know that others will! :)


Title: Re: Mathematical expression translator
Post by: Frontrunner on April 23, 2008, 05:25:53 PM
Hi Ralph,

You are to some part right!
But please forget about the C part, as long as the POW and the ^ operator are being translated correctly.
I am not here on a qbasic forum  for C coding  :D

Cheers,
Frontrunner


Title: Re: Mathematical expression translator
Post by: wildcard on April 23, 2008, 06:06:44 PM
I'm trying to dust off my head and have a go, I know its about parsing correcting but am confused by your original example:

r1 = (-b + (SQR(b(x) ^ 2 - (4 * a * c)))) / (2 * a)

Is b and b(x) an integer and an arrary respectively or am I miss reading, I've been out of maths and coding for too long :)


Title: Re: Mathematical expression translator
Post by: Frontrunner on April 23, 2008, 06:52:54 PM
Thank you for pointing me to the confusion.
I have changed the original example  ;D
b is indeed an array.

But you have seen it right that the challenge is all about an parsing correction!

Sorry for the confusion.

Kind regards,
Frontrunner


Title: Re: Mathematical expression translator
Post by: Ralph on April 23, 2008, 06:56:09 PM
There is nothing as good for explaining as one or more examples!  Could you post at least one, good example of a math expression and the qbasic equivalent code that you would want?  That would help a lot!!! :)


Title: Re: Mathematical expression translator
Post by: wildcard on April 23, 2008, 07:19:35 PM
Frontrunner: No problem, haven't got to using it yet though still working on the simpler bracket-less parser.

Ralph: The challenge is to write a converter/parser that changes x ^ y to pow(x,y) however in the context of a more complex equation such as posted.


Title: Re: Mathematical expression translator
Post by: Ralph on April 23, 2008, 11:51:58 PM
Thanks, Wildcard.  I've never tried things like this before.  At first thought, it would seem that the algorithm would look for each character ^, then, for each, compare the characters going backwards and consider where to stop, put a "(" there, then continue until either a "(" or any mathematical function is found; next, do the same, going forward.  If this is the way to do it, I can see I would flounder in all the considerations I would have to take into account!  It really is too much for me, and definetely, "Not my cup of tea!"


Title: Re: Mathematical expression translator
Post by: Frontrunner on April 24, 2008, 05:39:17 PM
Hi All...

Ralph I see you are understanding the problem quite good and your approach is also good.

As for your reference I will give another tricky example:

Basic
a = -x ^ 3 - 3 * x ^ 2 + 4 * x - (x ^ 3 + x ^ 2 - 2) * (-1)

C
a = -pow(x,3) - 3 * pow(x,2) + 4 * x - (pow(x,3) + pow(x,2) - 2) * (-1)

Kind regards,
Frontrunner


Title: Re: Mathematical expression translator
Post by: wildcard on April 24, 2008, 06:30:31 PM
It's proving to be a nice challenge for getting back into some coding. My parser is coming along nicely, just need to figure out how to cope with brackets and arrays.


Title: Re: Mathematical expression translator
Post by: Frontrunner on April 25, 2008, 07:23:32 AM
Hi Wildcard,

I am glad to see you are making good progress 8)

Cheers,
Frontrunner


Title: Re: Mathematical expression translator
Post by: Ralph on April 25, 2008, 11:40:45 AM
Frontrunner:

I am going to try to make the code to solve for the simple multiple occurrances of the general type. variable^power, which shouldn't be too difficult. 

Once I succeed, I will try to go one step farther, considering an array*power.

After that, I will publish a list of all the cases I can think of, and ask for input on other cases I will have missed.

As to your good-will post to Wildcard, whom I consider to be an Ace of a wildcard, ha, ha, it makew me think that Wildcard is the true "frontrunner".  Sorry for the lame pun, but I just couln't resist it!


Title: Re: Mathematical expression translator
Post by: Ralph on April 25, 2008, 04:40:46 PM
Frontrunner:

Though I'm not competing, here is my beginning code, with all my thoghts so far.  It seems to work fine for Example1.  If you approve it, I will code for Example2 and, maybe, Example3 :
Code:
'B2C-Tran is a QuickBASIC to C translator for the C "pow" (power) function.
'I have decide to produce the necessary QuickBASIC code for the challenge as
'posted by Frontrunner at:
'http://forum.qbasicnews.com/index.php?topic=13196.0
'on an example-by-example basis, as I am not a professional programmer, just an amateur piddler.
'Example1: x ^ n
'BASIC: a = x ^ n
'    C: a = pow(x, n)

'''TO BE COVERED LATER:
'Example2: b(x) ^ n
'   BASIC: a = b(x) ^ n
'       C: a = pow(v(x), n)

'Example3:
'   BASIC: r1 = (-c + (SQR(b(x) ^ 2 - (4 * a * c)))) / (2 * a)
'       C: r1 = (-c + (sqrt(pow(b(x), 2) - (4 * a * c)))) / (2 * a)

'============================================================================

'Program specifications:
'Program must convert the BASIC Example1 to its equivalent C code.

'============================================================================
'PROGRAM DESCRIPTION:
'BASIC expresion in which the power function "r = x ^ n" is to be convert to
'its equivalent C power function, "a = pow(x, n)".

'PROGRAM DEVELOPEMENT:
'1. Search the BASIC string, BAS$, for an instance of a power expression, "^".
'2. Once the "^" is found, proceed to the left, after the first " ":
'   a. If the next character is a not a ")", add it to the empty string, C$.
'   b. Add the C power function letters, "pow", to the front of the above
'      group of characters.
'   c. Proceed to the right, after  the first " "; add those characters to
'      the above expression, C$, until the next " " is found.  Done.
'3. Compare the C$ obtained with the correct expression contained in Ceq$.
'   Once a match is obtained, print it to screen.

'============================================================================

'CODE:
CLS

'for development stage, use "test = 1"
test = 0
'test = 1
'Expressions:
BAS$ = "a = x ^ n"
Ceq$ = "a = pow(x, n)"

'OBTAIN STRINGS TO USE
'leftSide$ = left side of BAS$, including the equals sign and a " ":
FOR i = 1 TO LEN(BAS$)
  a$ = MID$(BAS$, i, 1)
  IF a$ <> "=" THEN
    leftSide$ = leftSide$ + a$
  ELSE
    EXIT FOR
  END IF
NEXT i
leftSide$ = leftSide$ + "= "


'rightSide$ = string to the right of the equals sign:
FOR i = LEN(leftSide$) + 1 TO LEN(BAS$)
  rightSide$ = rightSide$ + MID$(BAS$, i, 1)
NEXT i

'dist = the position of "^" in string rightSide$
FOR i = 1 TO LEN(rightSide$)
  a$ = MID$(rightSide$, i, 1)
  IF a$ = "^" THEN dist = i: EXIT FOR
NEXT i

'leftChr$ = left characters for the C function
FOR i = dist - 2 TO 1 STEP -1
  a$ = MID$(rightSide$, i, 1)
  leftChr$ = a$ + leftChr$
NEXT i
leftChr$ = "pow(" + leftChr$ + ", "

'rightChr$ = right characters for the C function
FOR i = dist + 2 TO LEN(rightSide$)
  a$ = MID$(rightSide$, i, 1)
  rightChr$ = rightChr$ + a$
NEXT i
rightChr$ = rightChr$ + ")"

C$ = leftSide$ + leftChr$ + rightChr$

IF C$ = Ceq$ THEN
  PRINT " The C equivalent for the QB expression, "
  PRINT "    " + BAS$
  PRINT " is "; C$
ELSE
  PRINT " The result generated by the program,"
  PRINT "    "; C$
  PRINT " is wrong!  Program must be corrected. Notify the responsible person."
END IF

'----------------------------------------------------------------------------
'temporary troubleshooting code
  IF test = 1 THEN
PRINT
PRINT " BAS$ = "; CHR$(34); BAS$; CHR$(34)
PRINT " Ceq$ = "; CHR$(34); Ceq$; CHR$(34)
PRINT
PRINT " left side = "; CHR$(34); leftSide$; CHR$(34)
PRINT "right side = "; CHR$(34); rightSide$; CHR$(34)
PRINT "distance to ^ in rightSide$ ="; dist
PRINT " leftChr$ = "; CHR$(34) + leftChr$; CHR$(34)
PRINT "rightChr$ = "; CHR$(34) + rightChr$; CHR$(34)

  END IF
'----------------------------------------------------------------------------




GOSUB pause
SYSTEM

'============================================================================
'SUBROUTINES:

pause:
WHILE INKEY$ = "": WEND
RETURN


Title: Re: Mathematical expression translator
Post by: Frontrunner on April 25, 2008, 05:59:45 PM
whom I consider to be an Ace of a wildcard, ha, ha, it makew me think that Wildcard is the true "frontrunner".  ;D
Lol Ralph!

Thanks for your contribution so far.
The way you are tackling the problem is interesting but you have to consider that the conversion should work in all situations and not only with examples where assignments are included.

So you really need a parse engine to make this work.

But it is good to see you are doing your best!

Cheers,
Frontrunner


Title: Re: Mathematical expression translator
Post by: Ralph on April 25, 2008, 08:33:14 PM
What is a parse engine?


Title: Re: Mathematical expression translator
Post by: Frontrunner on April 26, 2008, 05:48:24 AM
Hi Ralph,

The parser is the main routine you in this challenge and is also called a parse engine.

Have a look at this link which will explain you some more on how a parser works:
http://forums.devshed.com/other-programming-languages-139/how-does-an-interpreter-compiler-work-312483.html

I hope that will help!

Cheers,
Frontrunner


Title: Re: Mathematical expression translator
Post by: Ralph on April 29, 2008, 12:30:37 AM
Thank you, Frontrunner, for your link.  I now have a fair idea of what a parser is.


Title: Re: Mathematical expression translator
Post by: LPG on April 29, 2008, 02:57:46 AM
I tried this from QB > C. i made it do this:
  • put spaces between expressions and operators
  • find the ^
  • search left until it finds a space. if it sees a ) forget spaces until it comes to a (
  • put "pow(" in
  • do the same going right but add ")"
  • put spaces in again

the only error is that it searches from left to right so for:
    (5^5)^5
it returns:
    (pow( 5, 5) )pow( ,5)
but for something like this:
    5^5
it returns:
    pow(5,5)

it should look from the inside brackets to the outside brackets but i don't know how to do that.

    LPG   
     


Title: Re: Mathematical expression translator
Post by: Frontrunner on April 29, 2008, 11:49:28 AM
You are very welcome Ralph, I am glad it helped!

Hi LPG,

If I may give you a tip ?
Use an array to split the whole input string in to tokens.
This makes it easier to keep track of symbols like brackets etc. and once you know where to place the pow statement you can simply change the array.

So (5^5)^5 could look like this:
Token$(1) = "("
Token$(2) = "5"
Token$(3) = "^"
Token$(4) = "5"
Token$(5) = ")"
Token$(6) = "^"
Token$(7) = "5"

To become pow((pow(5,5)),5)

Token$(1) = "pow" + Token$(1)
Token$(2) = "(pow(" + Token$(2)
Token$(3) = ","
Token$(4) = "5"
Token$(5) = ")" + Token$(5)
Token$(6) = ","
Token$(7) = Token$(7) + ")"

Note that all tokens which are ^ simply become a comma.
The trick is to take track of the brackets!

I hope that helps.

And then one more tricky example when it comes to unary operators ;)
If -8 - -5 = 1 - -2 ^ 2 Then
Becomes
If -8 - -5= 1- -pow(2,2) Then

Cheers,
Frontrunner



Title: Re: Mathematical expression translator
Post by: wildcard on April 29, 2008, 06:53:31 PM
Interesting post there Frontrunner, I've not had much time last few days to work on my entry but was stuck at the brackets stage still too anyway, will hopefully get some time to finish it soon.


Title: Re: Mathematical expression translator
Post by: Frontrunner on April 29, 2008, 07:06:20 PM
Hi Wildcard,

I hope it will help you to tackle the brackets.

Have a nice day.
Frontrunner


Title: Re: Mathematical expression translator
Post by: LPG on April 30, 2008, 01:06:44 AM
Thanks Frontrunner


Title: Re: Mathematical expression translator
Post by: Frontrunner on April 30, 2008, 06:27:43 AM
No problem, I hope it helped!

Have a sunny day  ;D
Frontrunner


Title: Re: Mathematical expression translator
Post by: Frontrunner on May 03, 2008, 11:16:27 AM
I am not sure how many of you are working on this challenge but I came along this website which might be interesting for those who use FreeBasic and want to solve this challenge.

http://www.runicsoft.com/fparser.php

Cheers,
Frontrunner



Title: Re: Mathematical expression translator
Post by: yetifoot on May 07, 2008, 11:37:01 AM
Hi all, stumbled across this challenge, it's right up my street!

Something I would say, is the rules and goals are not as clear as I'd like, should we be implementing everything that is possible in a QB expression?  What about things like / and \ which are different in C, you only have / and have to promote to float to cause an FP divide.  Are some things left-right or right-left? etc.

Anyway, that aside I put one together that seems to show most of what you want.  I prototyped it in FB, but it seems to work OK in the QB I have too.  It does the operator precedence (I hope..!, I'm not too sure on QB's exact precedence, and didn't fancy trial and erroring to find out, but i based it on FBs so it should be very close at least), has operators +, -, -(negate), /, \, *, ^, SQR, can deal with array or variables (arrays change to a[] syntax), it handles parenthesised sub expressions.  It might do some other stuff i forgot, or there may be features I implemented by accident when I added bugs :P

It is not optimal by a long shot, there are many things I could have done to it.  I could cut down the size of the code by rolling parseaddsub, parsemuldiv and others into one function, and using a table to control the operators.  I could have cut down on the strings.  I could have built a tree/stack from the expression in order to make it easy to optimize constants (ie (3 + 4) would become (7).  But I didn't.

Anyway, here's the code.
Code:
DECLARE FUNCTION parsenegate$ ()
DECLARE FUNCTION isdigit% (c AS INTEGER)
DECLARE FUNCTION isalpha% (c AS INTEGER)
DECLARE SUB skipwhite ()
DECLARE SUB readtoken ()
DECLARE FUNCTION parsefactor$ ()
DECLARE FUNCTION parsepow$ ()
DECLARE FUNCTION parsemuldiv$ ()
DECLARE FUNCTION parseidiv$ ()
DECLARE FUNCTION parseaddsub$ ()
DECLARE FUNCTION QB2C$ (s AS STRING)
DIM SHARED look AS INTEGER
DIM SHARED token AS STRING
DIM SHARED tokentype AS INTEGER
DIM SHARED buffer AS STRING
DIM SHARED bufferlen AS INTEGER
DIM SHARED bufferpos AS INTEGER

DECLARE SUB readchar ()
DECLARE FUNCTION parsetop$ ()

CONST TYPBAD = 0
CONST TYPOPERATOR = 1
CONST TYPNUMVAR = 2

'::::::::
' MAIN PROGRAM!

PRINT QB2C("((43 * 4) + 45 + 5 + 7 * 3 ^ 2) / 6 \ 3 + sqr( 54 - -4 ) + (--5) + B(54 + 3) - (-5) ^ 2")

'::::::::
FUNCTION isalpha% (c AS INTEGER)

isalpha = ((c >= ASC("a")) AND (c <= ASC("z"))) OR ((c >= ASC("A")) AND (c <= ASC("Z")))

END FUNCTION

'::::::::
FUNCTION isdigit% (c AS INTEGER)

isdigit = (c >= ASC("0")) AND (c <= ASC("9"))

END FUNCTION

'::::::::
FUNCTION parseaddsub$

DIM l AS STRING
DIM r AS STRING
DIM op AS STRING

l = parseidiv

WHILE (token = "+") OR (token = "-")
op = token
readtoken
r = parseidiv
l = "(" + l + " " + op + " " + r + ")"
WEND

parseaddsub = l

END FUNCTION

'::::::::
FUNCTION parsefactor$

DIM result$

IF tokentype = TYPNUMVAR THEN
result$ = token
readtoken
IF token = "(" THEN
readtoken
result$ = result$ + "[" + parsetop + "]"
IF token <> ")" THEN
PRINT "Expected parenthesis (4)"
END
END IF
readtoken
END IF
parsefactor = result$
ELSE
IF token = "(" THEN
readtoken
parsefactor = parsetop
IF token <> ")" THEN
PRINT "Expected parenthesis (1)"
END
END IF
readtoken
ELSEIF UCASE$(token) = "SQR" THEN
readtoken
IF token = "(" THEN
readtoken
parsefactor = "sqrt(" + parsetop + ")"
IF token <> ")" THEN
PRINT "Expected parenthesis (2)"
END
END IF
readtoken
ELSE
PRINT "Expected parenthesis (3)"
END
END IF
ELSE
PRINT "Bad factor: " + token
END
END IF
END IF

END FUNCTION

'::::::::
FUNCTION parseidiv$

DIM l AS STRING
DIM r AS STRING
DIM op AS STRING

l = parsemuldiv

WHILE (token = "\")
op = token
readtoken
r = parsemuldiv
l = "(" + l + " " + op + " " + r + ")"
WEND

parseidiv = l

END FUNCTION

'::::::::
FUNCTION parsemuldiv$

DIM l AS STRING
DIM r AS STRING
DIM op AS STRING

l = parsenegate

WHILE (token = "*") OR (token = "/")
op = token
readtoken
r = parsenegate
l = "(" + l + " " + op + " " + r + ")"
WEND

parsemuldiv = l

END FUNCTION

'::::::::
FUNCTION parsenegate$

DIM l AS STRING
DIM r AS STRING

IF token = "-" THEN
readtoken
r = parsetop
l = "(-" + r + ")"
ELSE
l = parsepow
END IF

parsenegate = l

END FUNCTION

'::::::::
FUNCTION parsepow$

DIM l AS STRING
DIM r AS STRING

l = parsefactor

WHILE (token = "^")
readtoken
r = parsefactor
l = "pow(" + l + ", " + r + ")"
WEND

parsepow = l

END FUNCTION

'::::::::
FUNCTION parsetop$

parsetop = parseaddsub

END FUNCTION

'::::::::
FUNCTION QB2C$ (s AS STRING)

buffer = s
bufferlen = LEN(s)
bufferpos = 0

readchar
readtoken

QB2C = parsetop

IF token <> "<<<EOF>>>" THEN
PRINT "Something went wrong!"
END
END IF

END FUNCTION

'::::::::
SUB readchar

IF bufferpos < bufferlen THEN
look = ASC(MID$(buffer, bufferpos + 1, 1))
bufferpos = bufferpos + 1
ELSE
look = -1
END IF

END SUB

'::::::::
SUB readtoken

skipwhite

token = ""
tokentype = TYPBAD

IF (isdigit(look)) OR (look = ASC(".")) THEN
WHILE (look <> -1) AND (isdigit(look) OR look = ASC("."))
token = token + CHR$(look)
readchar
WEND
tokentype = TYPNUMVAR
ELSEIF isalpha(look) THEN
WHILE (look <> -1) AND isalpha(look)
token = token + CHR$(look)
readchar
WEND
tokentype = TYPNUMVAR
SELECT CASE UCASE$(token)
CASE "SQR"
tokentype = TYPOPERATOR
END SELECT
ELSE
SELECT CASE look
CASE ASC("+"), ASC("-"), ASC("\"), ASC("/"), ASC("*"), ASC("^"), ASC("("), ASC(")")
token = CHR$(look)
readchar
tokentype = TYPOPERATOR
CASE -1
token = "<<<EOF>>>"
tokentype = TYPBAD
CASE ELSE
PRINT "Bad character detected: '" + CHR$(look) + "'"
END
END SELECT
END IF

PRINT "token: '" + token + "'"

END SUB

'::::::::
SUB skipwhite

WHILE (look <> -1) AND (look = ASC(" "))
readchar
WEND

END SUB


Title: Re: Mathematical expression translator
Post by: Frontrunner on May 07, 2008, 07:23:42 PM
Hi Yetifoot,

Thank you for your contribution!
I can see you have done this before :D

Regarding your questions:
The language/compiler/interpreter/translator  can be called anything as long as the syntax is close to qbasic so your code looks pretty fine to me.

The type of parsing is free to choose from so left-right or right-left, bottom-up, top-down all are fine, as long as the output is correct.

You have a good point regarding the float and integer division operators, the last one doesn't exists in C.
Example:
PRINT 11 - (4 * FIX(11 / 4))
PRINT 11 / 4
PRINT FIX(11 / 4)
PRINT 9 / 3
PRINT FIX(9 / 3)
PRINT 67 / -3
PRINT FIX(67 / -3)

Result Qbasic
 3
 2.75
 2
 3
 3
-22.3333
-22

Result Visual Basic and C
 3
 2
 2
 3
 3
-22
-22

Actually the result is not different in C but it doesn't show the correct output unless you explicit tell to output in float format.

I hope I explained things somewhat better now  ::)

I didn't yet look very attentively to your code but so far it looks good, well done!

Cheers,
Frontrunner


Title: Re: Mathematical expression translator
Post by: wildcard on May 13, 2008, 10:26:26 AM
I haven't forgotten about the challenge, just havent' had much time lately. Got a fair bit still to do to make a proper parser though, but am interested in finishing it as would like to have a go making a simple basic like scripting language.


Title: Re: Mathematical expression translator
Post by: Frontrunner on June 01, 2008, 06:23:07 PM
Hi Wildcard,

I am still waiting for your submission  :)
It's good to see that this challenge has given you a push to create a scripting language, I am looking forward to see the result!

Cheers,
Frontrunner


Title: Re: Mathematical expression translator
Post by: wildcard on June 04, 2008, 04:29:50 AM
Frontrunner: I haven't forgotten about the challenge, I'm still working on my entry when time allows.


Title: Re: Mathematical expression translator
Post by: Agamemnus on August 05, 2008, 05:17:38 PM
I tried this from QB > C. i made it do this:
  • put spaces between expressions and operators
  • find the ^
  • search left until it finds a space. if it sees a ) forget spaces until it comes to a (
  • put "pow(" in
  • do the same going right but add ")"
  • put spaces in again

the only error is that it searches from left to right so for:
    (5^5)^5
it returns:
    (pow( 5, 5) )pow( ,5)
but for something like this:
    5^5
it returns:
    pow(5,5)

it should look from the inside brackets to the outside brackets but i don't know how to do that.

    LPG   
     

The way you described it won't work with the second example either.

You did do the right thing by going left to right, I think.

A few pointers of my own:
* Instead of adding spaces you could instead remove them. It is less mess when you try to parse it later.
* In the same manner, it's less trouble to parse later when you add ()s between the start and end of numbers that have ^ powers. So 5^2 would become (5)^2.

GENERAL pointers:
* You can either do an iterative parser or a recursive parser: a recursive parser would try to find whole power sets and recursive deeper for each new one, while an iterative parser would have to keep track of the "tree"...

Find the end of the expression (in this case ")^"), then find its end. In either recursive or iterative case, you keep searching for either the start of the expression (a "(") or the "end" of a new one --")^". In either case you need to counting non-power ending parentheses and ignore a corresponding amount of starting parentheses.
It gets just a little bit complicated but basically you want to be able to parse something like "(5*(5+2))^5"...