RPN Enbafflement

-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0\|617\|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
Socoder -> Misc Languages -> RPN Enbafflement
Tue, 06 Apr 2021, 06:45
Jayenkai	RPN Enbafflement Wrapping myself up into knots, trying to figure this one out. Anyone want to give it a try!?! The Challenge Convert something like this.. Print 1+3Sin(Mills()/8)-6/2+" is probably not "+42 Into something like this.. Print((1 (3 Sin(Mills() 8 /) ) + (6 2 /) - ) " is probably not " + 42 +) --v Rules 1. Must take BODMAS into account. 2. Must ignore strings, and parse those at the correct time. 3. Should wrap everything into brackets, because apparently my script engine needs brackets around any maths!! 4. Must not cause my hair to fall out. Have at, code army!! -=-=- ''Load, Next List!''
Tue, 06 Apr 2021, 07:32
cyangames	Ohh, is this for your scripting engine?
Tue, 06 Apr 2021, 09:05
Jayenkai	Yeah, it was something I left until later, 'cos I thought it'd be a case of "Meh, just swapping bits about... that's EASY!!" .. D'oh! -=-=- ''Load, Next List!''
Sun, 11 Apr 2021, 18:20
shroom_monk	I've taken a stab at this, but either I'm missing something or I think I've identified a few issues with the problem as stated. Firstly, to be truly RPN I think that all functions need to be treated like operators. So Sin(x/8) --v should be x 8 / Sin --v for example, rather than Sin(x 8 /) --v Secondly, the meaning of the + operator is context dependent in your example: it means both addition of numbers and concatenation of strings. On its own this isn't a problem if you only care about one type or the other, but because you can mix and match types, you can get problems with reordering. For example: 1+3Sin(Mills()/8)-6/2+" is probably not "+42 --v wants to be interpreted something like: Calculate the value of 1+3Sin(Mills()/8)-6/2 Convert the result to a string Concatenate the above string with " is probably not " and "42" --v But because - is technically lower precedence in BODMAS than +, then a RPN parser will want to do the subtraction in the above calculation last, as it can't tell the difference between addition + and concatenation +. Solving this requires the context of each + to be figured out ahead of time, which is painful. As a final note, I think true RPN doesn't require brackets at all? In theory you can add them back in afterwards, but the fact that functions (e.g. Sin) still require brackets in your notation makes this trickier. So I think that might be why you've got yourself tangled in knots! Anyway, here's my attempted solution to the problem, in Python. There are two steps. First we 'tokenise' the input, i.e. split it up into an array of strings where each string is a meaningful 'token', which we label. Secondly we convert these tokens into RPN using the Shunting-yard Algorithm, except modified to account for aforementioned quirks. Unfortunately it doesn't quite work on your sample input due to the issue with operator precedence I mentioned! And I didn't do the bracketing thing because of the trickiness with functions not being in reverse. code = 'Print 1+3Sin(Mills()/8)-6/2+" is probably not "+42' # Stuff for handling operators operators = '()^/+-' # Note these are in BODMAD order, and we assume operators are all single characters! def opGreaterOrEqualPrecedence(a, b): global operators # N.B. lower index means higher precedence precedenceA = operators.index(a) precedenceB = operators.index(b) return precedenceA <= precedenceB # ================ # Step 1: Tokenise # ================ # We're going to build up a list of 'tokens' # Each token looks like: (string, token_type) tokens = [] tokenInProgress = '' # Types of tokens token_none = 0 token_identifier = 1 # (could be a command, function name, variable name, etc) token_number = 2 token_string = 3 token_operator = 4 currentTokenType = token_none # Helper to finish the current token def completeToken(): global tokens global tokenInProgress global currentTokenType tokens.append((tokenInProgress, currentTokenType)) tokenInProgress = '' currentTokenType = token_none # Look at each character in the input index = 0 while index < len(code): char = code[index] # Identify what kind of token is next if currentTokenType == token_none: if char.isalpha(): currentTokenType = token_identifier elif char.isnumeric(): currentTokenType = token_number elif char == '"': currentTokenType = token_string elif char in operators: currentTokenType = token_operator elif char.isspace(): # Skip whitespace index += 1 else: print('Error, cannot parse character {0}'.format(char)) # Identifier token (must start with a letter but can include digits and underscores) elif currentTokenType == token_identifier: if char.isalnum() or char == '_': tokenInProgress += char index += 1 else: completeToken() # Number token (digits, possibly including decimal point) elif currentTokenType == token_number: if char.isnumeric() or char == '.': tokenInProgress += char index += 1 else: completeToken() # String token (wrapped by double quotes; note that this version doesn't handle escaping!) elif currentTokenType == token_string: tokenInProgress += char index += 1 if char == '"' and tokenInProgress != '"': completeToken() # Operator token (any operator; we assume these are single characters for simplicity) elif currentTokenType == token_operator: tokenInProgress += char index += 1 completeToken() # If a token is still in progress, complete it if currentTokenType != token_none: completeToken() # Show the results of tokenisation print('Results of tokenisation step:') print(tokens) print() # ======================================= # Step 2: Sort-Of Reverse Polish Notation # ======================================= # Sort-Of the Shunting-yard Algorithm, but not quite # https://en.wikipedia.org/wiki/Shunting-yard_algorithm # (ignores functions, assumes all operators are left-associative) outputQueue = [] operatorStack = [] for token in tokens: (tokenString, tokenType) = token if tokenType == token_operator: if tokenString == '(': operatorStack.append(tokenString) elif tokenString == ')': while operatorStack and operatorStack[-1] != '(': outputQueue.append(operatorStack.pop()) if not operatorStack: print('Error, mismatched brackets') else: operatorStack.pop() else: while operatorStack and opGreaterOrEqualPrecedence(operatorStack[-1], tokenString) and operatorStack[-1] != '(': outputQueue.append(operatorStack.pop()) operatorStack.append(tokenString) else: outputQueue.append(tokenString) while operatorStack: outputQueue.append(operatorStack.pop()) # Show the RPN results print('RPN:') print(outputQueue) --v Maybe you can adapt the above into something useful! Addressing the issues noted might make things easier or there might be some other way around it (or maybe I'm totally wrong, it is 1am after all). As an aside, I vaguely recall that stuff like Context Free Grammars get called out as good ways to parse programming languages, but I've forgotten too many of the important details to be able to blindly recommend those. Could be worth researching if you're interested though. -=-=- A mushroom a day keeps the doctor away... Keep It Simple, Shroom!
Sun, 11 Apr 2021, 18:31
Jayenkai	I'll have a try in the morning, thanks Shroomy! FWIW, the command is most definitely coming at the end. What I'm doing is parsing a line, popping elements into a mini-script, and then running through that. Print 1+2+3 becomes 1 - n1 2 - n2 3 - m+ (adds 1 and 2, puts into 1) 4 - n3 5 - m+ (adds 1 and 4, puts into 1) 6 - Print (value at 1) It's incredibly convoluted, and the code is becoming completely unmanageable. I'll have a read through your post and see if it clicks anything important. Thanks again. distant ascii hugs -=-=- ''Load, Next List!''
Mon, 12 Apr 2021, 05:06
Pakz	I have this book called "language implementation patterns" It is a book on how to write your own various compilers/parsers. I only read a bit and need to really sit down and read it when I want to do something like that. I was thinking of creating some kind of scratch interface for a minecraft game and/or civ game. From one thing in there I noticed the author took the lines of code apart and placed them into a stack list and handled the logic from the stack. It is still way out of my understanding though.
Mon, 12 Apr 2021, 07:04
Jayenkai	Got it to this stage.. Print 1 + 2 * 3 + " Test " + Pyth(1,2) // Where Pyth = Sqr((aa)+(bb)) Print 1 2 + 3 * " Test " + Pyth + 1( , 2 ) --v Nnngh. You're definitely right about those bracketed command'y bits! I'll study more!! -=-=- ''Load, Next List!''
Mon, 12 Apr 2021, 10:43
Jayenkai	Almost got things working, but a few stragglers are clinging on.. Print 5=<5 isn't working, because the parser is currently splitting the = and the <.. Should be an easy enough fix... I hope! Rect 32,32,100-32,100-32 isn't working, because the maths in each parameter is still trying to access "value 0", which is the first parameter. I need to rejig my parameter stuff, and hope I can figure it out. Rect 32,32,Pyth(90,100-10),Pyth(80,70-5) makes things infinitely worse, with parameter-based maths and function calls and more, all confusing the hell out of the poor script!! // String Tests // by Jayenkai // Created 2021/3/7 Graphics 640,480,2 Repeat CLS; SetCol(0,0,128); Rect 0,0,ScreenWidth(),ScreenHeight(); Print SetHue(60,1,1); Print 1+23+" <-- (BODMAS) Issue! .. Haven't even tackled this, today!" Print "1+2+3="+(1+2+3)+" <-- Bafflingly Broken!" Print "[[ "+123+" Hello World "+(15324)+" ]] <-- Given that this works.." Print Mills() % 1000 < 500+" <-- This ticks like it oughta" Text 320,200,ScreenWidth(),1 Text 320,240,ScreenHeight()+"<--Broken",1 // The number's up on the top left of the screen..!?! // The string is nowhere to be seen..!!!!!? Flip Forever --v -=-=- ''Load, Next List!''