Qbasicnews.com
April 21, 2018, 08:51:48 AM *
Welcome, Guest. Please login or register.

Login with username, password and session length
News: Back to Qbasicnews.com | QB Online Help | FAQ | Chat | All Basic Code | QB Knowledge Base
 
   Home   Help Search Login Register  
Pages: 1 2 [3]
  Print  
Author Topic: Mathematical expression translator  (Read 30692 times)
yetifoot
Ancient Guru
****
Posts: 575



« Reply #30 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 Tongue

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
Logged

EVEN MEN OF STEEL RUST.
Frontrunner
New Member

Posts: 16


« Reply #31 on: May 07, 2008, 07:23:42 PM »

Hi Yetifoot,

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

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  Roll Eyes

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

Cheers,
Frontrunner
Logged
wildcard
*.*
Administrator
__/--\__
*****
Posts: 2365



« Reply #32 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.
Logged
Frontrunner
New Member

Posts: 16


« Reply #33 on: June 01, 2008, 06:23:07 PM »

Hi Wildcard,

I am still waiting for your submission  Smiley
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
Logged
wildcard
*.*
Administrator
__/--\__
*****
Posts: 2365



« Reply #34 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.
Logged
Agamemnus
x/ \z
*****
Posts: 3491



« Reply #35 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"...
Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Pages: 1 2 [3]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines Valid XHTML 1.0! Valid CSS!