Reverse Polish

[Toot]

Now then. I've got an expression builder that builds expressions (so far so good) in a normal boolean way like:
((w AND x) OR y) AND (NOT z)
and I need to get it into reverse polish, which would look like (as far as I can gather):
w x AND y OR z AND NOT
Correct me if I'm wrong

Actually getting it into reverse polish isn't my main concern (at the moment) - I'm just struggling a bit to see how I'm going to balance all the brackets properly. Has anyone ever tried to do anything like this in VB? I could do it in at least two other languages but that doesn't help me whatsoever 'cos it has to be in VB!

Any help would be greatly appreciated!

Toot

[HarryW]

Actually the syntax would be

w x AND y OR z NOT AND


Usually you would use a recursive function for this I think.

You have a function which extracts the expression in the brackets when you parse to a left (opening) bracket and calls your original function to evaluate an expression, returning the result which you place on the stack. I'm assuming you're doing this with a stack of some sort.

[Sam Finch]

Could you explain the rules of reverse polish, I've never heard of the technique before, I'm thinking of doing some work in this area, so If you could explain this that'd be great.

[PaulLewis]

Someone posted recently asking about regular expressions and this is another time when they would be handy!

I've done a calculation bean in Java (also no native support for Regular expressions) and it was quite lengthy.

But I had to support an extensible list of functions as well as the normal logical and mathematical operators so your case should be alot more straight forward...

HAving said that, I'm glad it's you and not me

As a test though, if you respond to Sam's request for the rules for reverse Polish, then maybe a few of us could write something as a sort of mini-contest

That ought to put the cat amongst the pigeons!

Cheers
Paul Lewis

1 + 2

would be written as.......

C;2;1;+

Is that any help??????????

[PaulLewis]

It's just like an old old fashioned adding machine... the machine can take two values followed by an operator. The resulting value is left in the machine to be used as the next "first" value.

It would seem to be a way to remove the brackets from complex equations then?

Too late for me anyhow since it's 4pm on a Friday so I'm off home.

Cheers

Paul Lewis

[Toot]

Well, if anyone's still interested in knowing exactly what RPN is, take a quick peak at http://www.whisqu.se/per/docs/math35.htm. Basically it's a notation that takes away the need for brackets while ensuring unambiguosity (is that a word?!)

I'm still a bit unsure how to start though, so any tips would be fantastic.

Toot

[Iain17]

Toot,

Very intriguing question. I think that the answer will turn out to be quite complicated however.

This is my first attempt at solving the problem. There will be others unless someone (probably Sam), beats me to it. Once i have got the logic in my head sorted out, i may be able to do it in VB. Though once you get into it, it is harder than you expect.


This code sort of works. It will work on complicate expressions, but it has a long way to go yet, but seeing as you asked for somewhere to start, i am going to post it. Though it may turn out to be the wrong way to go about things.

N.b. It needs brackets. Every operation should be enclosed in brackets. e.g.

5 * 5 * 5

should be input as

(5 * (5 * 5))

Any way, i am sure you will see that it doesn't work on all expressions, but it is a start.

Option Explicit

'Sin(123 + (45 * (ln(27 - 6))))
'should end up as.
'sin(+(123,*(45,ln(-(27,6)))))


Private Function revPolish(strExp As String) As String
    Dim ip1 As Integer, ip2 As Integer
    Dim strTemp As String
    
    ip1 = 1: ip2 = Len(strExp)
    Do
      ip1 = InStrRev(strExp, "(", ip2)
      If ip1 = 0 Then
        revPolish = strExp & "(" & revPolish & ")"
        Exit Do
      End If
      ip2 = InStr(ip1, strExp, ")")
      
      'get the string from the brackets
      strTemp = Mid$(strExp, ip1 + 1, ip2 - ip1 - 1)
      
      revPolish = getExpresion(strTemp) & revPolish & ")"
      
      'remove the expresion that has been done
      strTemp = Mid$(strExp, 1, ip1 - 1)
      strTemp = strTemp & Right$(strExp, Len(strExp) - ip2)
      strExp = strTemp
      
      ip2 = ip1 - 1
      
    Loop Until strExp = ""
    
    
End Function


Private Function getExpresion(strExp As String) As String
    Dim ip1 As Integer, ip2 As Integer
    Dim i As Integer
    
    If InStr(1, strExp, " ") > 0 Then
      
      'find a nonnumerical non space character
      For i = 1 To Len(strExp)
        If (Not IsNumeric(Mid$(strExp, i, 1))) And (Mid$(strExp, i, 1) <> " ") Then
          Exit For
        End If
      Next i
      
      'build the expresion
      getExpresion = Mid$(strExp, i, 1) & "("
      getExpresion = getExpresion & Mid$(strExp, 1, i - 1) & ","
      getExpresion = getExpresion & Right$(strExp, Len(strExp) - i)
    Else
      getExpresion = strExp & "("
    End If
    
End Function

Private Sub cmdGo_Click()
    
    txtOutput = revPolish(txtInput.Text)
    
End Sub

[HarryW]

Basically you parse the expression, adding values to a stack when you encounter them. When you get to an operator you pop the appropriate number of values off the stack, do the operation, then push the result back onto the stack. It's pretty simple really.

Toot, did what I said before help? I'm not actually sure I understood the question. I'm pretty sure the easiest way of doing this is recursive functions.

[Toot]

Sorry I've spent the afternoon so far struggling to get a corrupted form back out of sourcesafe (which, it turns out, should have been called sourceruin but I digress)...

OK I'll give those funcs a go later - thanks for the time & effort folks. What I've come up with so far is a general algorithm ("borrowed" from renoir.vill.edu):

While the input string is not empty 
	Read a symbol from the infix string 
	If the symbol is (, push it onto the stack. 
	If the symbol is ), pop the stack until ( is found. (Do not write the ()'s to the output string) 
	If the symbol is an operand, write it to the output string 
	If the symbol is an operator 
		While the top of stack contains an operator of higher precedence than the input symbol, pop the stack to the output string. 
		Push the input symbol onto the stack 
Pop the stack to the output string

So now I think all I've got to do is put that into basic and then check against Iain's way to see the difference and then tweak a bit to allow for the fact it's going to be used by everyday users!

Thanks again all, I'm on a course next week so if the thread's still alive when I get back I'll let you know how it all goes (the code, not the course)

Toot

[Toot]

...I missed your post completely there. Yeah what you said does make sense - I was presuming I'd have to do recursion of some sort or another, the real thing that was bothering me was matching brackets, considering the expression doesn't necessarily have to be entirely enclosed in them. But using a stack kinda eliminates the need to worry about it so that's good

Anyway, thanks for your input.

Toot

[Sam Finch]

OK, My Browser's managed to fine the Page, Which helps, I might have a bash at Coding Something.