Here is a limited algorithm for converting infix notation to RPN notation. The algorithm has no way of handling unary minuses (indicating negative numbers) nor does it deal with functions such as SIN(), COS(), SQR(), etc. I describe one way of handling unary minus in the comments of the program listing below and will alter the code to handle those as well as sines, cosines, square roots, etc. at a later date. In the mean time if you need an infix to RPN converter, this should handle most of your needs.
Parsing from left to right, any numeric value we encounter or any alphanumeric string that could be interpreted as a variable is sent directly to the output, including decimal points.
When we encounter anything other than numbers or letters (or a decimal point), we do the following:
Append a token separator to the output string (in our case a comma.)
If we encounter an open parenthesis, that parenthesis is pushed to a FILO stack.
If we encounter a closing parenthesis, we discard it and pop operators from the stack to the end of the output string until we come to an open parenthesis. The open parenthesis is then also discarded.
If we encounter a low priority operator (+ or -) then we must first pop all operators (+, -, *, /, ^) from the stack to the end of the output string until the stack is empty or we encounter an open parenthesis and then push the low priority operator on to the stack.
If we encounter a medium priority operator (* or /) then we must first pop any medium or high priority operators (*, /, ^) from the stack to the end of the output string until the stack is empty or we encounter a low priority operator (+ or -) or we encounter an open parenthesis, then push the medium priority operator on to the stack.
If we encounter a high priority operator (^) we pop all other high priority operators from the stack to the end of the output string then push the new high priority operator to the stack.
Once all the input character have been processed, we pop operators off the stack until it's empty.
The listing below shows a Visual Basic implementation of the algorithm:
'
' Infix to RPN - program to convert infix notation to
' RPN notation. Operands are separated by commas, to
' use a different separation character change the
' line where txtSeparator is initialized. The operator
' stack has been set to an upper limit of 100 operators,
' if you expect to have input strings with more than 100
' operators (heaven forbid...) increase the size of
' txtStack in the Dim statement.
'
' This routine does not handle unary minus signs. To allow
' unary minus signs two additional changes must be made. In the
' Low Operator case (+, -) we must check to see if the previous
' input character was an alphanumeric. If it IS alphanumeric
' we treat the minus as a normal binary operator. If it is NOT
' alphanumeric, then we append a zero and token separator to the
' output string, and push a special unary minus character to the
' stack, which has an operator value equal to ^. You can use the
' tilde "~" as the unary minus character since it's not being used
' for anything else. I'll make this changes to the routine at a
' later date.
'
' Written by - Erik Oosterwal
' Started on - Nov. 14, 2005
' Completed on - Nov. 15, 2005
Dim txtSeparator, txtStack(100), txtCharacter As String ' Declare all variables
Dim intPointer, intStackPointer As Integer ' used in the routine
txtSeparator = "," ' Set the token separator to a comma
intPointer = 1 ' Start by looking at the first character in the input string
intStackPointer = 1 ' Start the operator stack at 1
txtOutput.Text = "" ' Clear the output sting
While intPointer <= Len(txtInput.Text) ' As long as there's characters in the string
txtCharacter = Mid$(txtInput.Text, intPointer, 1) ' get the next character.
Select Case txtCharacter
Case "0" To "9", ".", "A" To "Z", "a" To "z" ' Numbers and variables get appended
txtOutput.Text = txtOutput.Text + txtCharacter ' directly to the output string.
Case "("
txtStack(intStackPointer) = txtCharacter ' Open parentheses get pushed on the stack
intStackPointer = intStackPointer + 1
Case ")" ' If we find a closing parenthesis
While intStackPointer > 1 And _
txtStack(intStackPointer - 1) <> "(" ' Clear the stack until we
txtOutput.Text = txtOutput.Text + txtSeparator + _
txtStack(intStackPointer - 1) ' get to the opening parenthesis.
intStackPointer = intStackPointer - 1
Wend
intStackPointer = intStackPointer - 1 ' Decrease the stack pointer to overwrite the opening parenthesis.
Case "+", "-" ' Lowest operators
txtOutput.Text = txtOutput.Text + txtSeparator ' Append a token separator to the output string.
' If there are any operators on the stack AND they're higher or equal valued than + and -, then...
' pop them off the stack and append them to the output string.
While intStackPointer > 1 And _
txtStack(intStackPointer - 1) <> "("
txtOutput.Text = txtOutput.Text + _
txtStack(intStackPointer - 1) + txtSeparator
intStackPointer = intStackPointer - 1
Wend
txtStack(intStackPointer) = txtCharacter ' Push the low operator on the stack.
intStackPointer = intStackPointer + 1
Case "*", "/" ' Medium operators
txtOutput.Text = txtOutput.Text + txtSeparator ' Append a token separator to the output string.
' If there are any operators on the stack and they're higher or equal valued than * and /, then
' pop them off the stack and append them to the output string.
While intStackPointer > 1 And _
(txtStack(intStackPointer - 1) = "*" Or _
txtStack(intStackPointer - 1) = "/" Or _
txtStack(intStackPointer - 1) = "^")
txtOutput.Text = txtOutput.Text + _
txtStack(intStackPointer - 1) + txtSeparator
intStackPointer = intStackPointer - 1
Wend
txtStack(intStackPointer) = txtCharacter ' Push the medium operator on the stack.
intStackPointer = intStackPointer + 1
Case "^" ' High operators
txtOutput.Text = txtOutput.Text + txtSeparator ' Append a token separator to the output string.
While intStackPointer > 1 And _
txtStack(intStackPointer - 1) = "^"
txtOutput.Text = txtOutput.Text + _
txtStack(intStackPointer - 1) + txtSeparator
intStackPointer = intStackPointer - 1
Wend
txtStack(intStackPointer) = txtCharacter ' Push the high operator on the stack.
intStackPointer = intStackPointer + 1
' There is no default case included in this routine. Any characters not explicitly taken care
' of by the cases will be ignored as whitespace. Some characters, such as x, #, and others
' that are used to denote binary, hex, octal, etc. numbers could be taken care of in the first
' case where numeric and alpha tokens are handled. It's ok to ignore spaces, tabs and other
' white space.
End Select
intPointer = intPointer + 1 ' Set the pointer to look at the next character
Wend
' All the input characters have been taken care of, now it's time to clear the stack.
'
While intStackPointer > 1 ' As long as there's still operators on the stack
txtOutput.Text = txtOutput.Text + txtSeparator + _
txtStack(intStackPointer - 1) ' Take one off and append it to the output string
intStackPointer = intStackPointer - 1 ' look at the previous operator
Wend
End Sub
No comments:
Post a Comment