-
Nov 15th, 2014, 12:57 AM
#1
[RESOLVED] Expression Evaluator - Parenthesis and Negatives
Hi y'all. I'm ultimately working towards a parser, but I figured that I'd start small and create an expression evaluator. This is what I have so far:
Code:
Private operators() As String = {"-", "+", "/", "*", "^"}
Public Function EvaluateExpression(ByVal expression As String) As Double
For i As Integer = 0 To operators.Length - 1
'Chose an operator to check
Dim sign As String = operators(i)
'Get the last instance of the operator
Dim lastPosition As Integer = expression.LastIndexOf(sign)
If lastPosition > -1 Then
'If there's an instance of the operator, then begin the recursion
Dim part1 As String = expression.Substring(0, lastPosition - GetSpacesBefore(lastPosition, expression))
Dim part2 As String = expression.Substring((lastPosition + 1) + GetSpacesAfter(lastPosition, expression))
'Calculate the left and right part of the expression based on the operator
If sign = "-" Then
Return EvaluateExpression(part1) - EvaluateExpression(part2)
ElseIf sign = "+" Then
Return EvaluateExpression(part1) + EvaluateExpression(part2)
ElseIf sign = "/" Then
Return EvaluateExpression(part1) / EvaluateExpression(part2)
ElseIf sign = "*" Then
Return EvaluateExpression(part1) * EvaluateExpression(part2)
Else
Return EvaluateExpression(part1) ^ EvaluateExpression(part2)
End If
End If
Next
'There are no operators, return the value
Return CDbl(expression)
End Function
Private Function GetSpacesBefore(ByVal index As Integer, ByVal input As String) As Integer
Dim counter As Integer = 0
For x As Integer = index To 0 Step -1
If input(x) = " " Then
counter += 1
Else
Return counter
End If
Next
Return 0
End Function
Private Function GetSpacesAfter(ByVal index As Integer, ByVal input As String) As Integer
Dim counter As Integer = 0
For x As Integer = index To input.Length - 1
If input(x) = " " Then
counter += 1
Else
Return counter
End If
Next
Return 0
End Function
It allows the user to enter in an expression with however many spaces between the digits and the operators without the spacing being consistent. It follows PEMDAS, but what it does not account for is parenthesis which overrides PEMDAS and negative numbers. Right now as it sits, my code would produce a syntax error if the user attempted:
Because it would literally translate it to one plus minus one, which syntactically is invalid.
With this being the math forum, I figured that I'd ask it here. How would I account for those two issues?
-
Nov 15th, 2014, 01:15 AM
#2
Re: Expression Evaluator - Parenthesis and Negatives
Hi,
Just use a DataTable’s compute Method which is a fully functional Expression Evaluator:-
vb.net Code:
Dim dt As New DataTable MsgBox(dt.Compute("1 + -1", Nothing))
Hope that helps,
Cheers,
Ian
-
Nov 15th, 2014, 03:19 AM
#3
Re: Expression Evaluator - Parenthesis and Negatives
I feel I should have a disclaimer at the top of this post. Namely, you probably shouldn't have to write your own parser nowadays and should instead be able to use someone else's; if you do have to write a parser there are formal grammar options which have been thought through and time-tested, so again you should probably go read a book on parsers instead of reinventing the wheel; and finally it's more of a CS question than a math question, it's just that your grammar happens to be math-based at the moment.
In any case, I'd say you need to break things up into more steps. Parsing is usually a two-step process. Lexing is the first step, i.e. breaking input into logical chunks like "(", "1", "+", "-5.3", ")". Actual parsing is the next step, where you try to make logical sense of the list of chunks from lexing. Doing this sort of pre-processing could be used to fix your 1 + -1 issue. During the parsing step, it's almost certainly best to create an "abstract syntax tree" which logically represents the input, which can then be evaluated. For instance, "3 * (4 + 5 ^ 2) + -1" could first be lex'd as "3", "*", "(", "4", "+", "5", "^", "2", ")", "+", "-1". You could then recursively build up a tree, eg.
Code:
"+"
/ \
"*" "-1"
/ \
"3" "+"
/ \
"4" "^"
/ \
"5" "2"
After you've constructed the parse tree it's very easy to write a recursive evaluation routine. Actually building the parse tree takes a bit of thought, though it's really not too bad. Mostly you have to match some parens and tell the computer how to handle precedence order. It's pretty similar to what you've already done, just more general.
To add parens in to your current code, I suppose you really just want the rightmost operator which is right of the rightmost right paren, eg. given (1+2)*3, you don't want + since there's a ) to its right, but you do want * since there's no ) to its right. There are some other issues to deal with, eg. (1) should evaluate to 1. I think it's not worth the time to try hacking this method together and that you should instead either reuse other people's code or write a basic lexer/parse tree creator.
The time you enjoy wasting is not wasted time.
Bertrand Russell
<- Remember to rate posts you find helpful.
-
Nov 15th, 2014, 03:57 PM
#4
Re: Expression Evaluator - Parenthesis and Negatives
Just use a DataTable’s compute Method which is a fully functional Expression Evaluator
Ideally I'd like to create my own. I'm really trying to understand how everything works.
that you should instead either reuse other people's code or write a basic lexer/parse tree creator.
I have the lexer part down no issue. My biggest issue has been the parser. I've tried reading up on many different PDFs as well as I've purchased the dragon book, but I am having the biggest difficulty creating the parser.
-
Nov 15th, 2014, 04:13 PM
#5
Re: Expression Evaluator - Parenthesis and Negatives
Go here next. It's meaningful and will allow you to forget problems like parens
http://en.wikipedia.org/wiki/Reverse_Polish_notation
-
Nov 16th, 2014, 06:58 PM
#6
Re: Expression Evaluator - Parenthesis and Negatives
RPN probably isn't an option here since that would force users to enter unusual syntax.
The shunting-yard algorithm is probably what you're after here. The example and description at the link are for converting to RPN, though you could just as well evaluate each time you pop an operator to the output queue and skip the RPN step in favor of direct evaluation. You can also modify it to spit out a syntax tree.
Is this what you're after?
The time you enjoy wasting is not wasted time.
Bertrand Russell
<- Remember to rate posts you find helpful.
-
Nov 16th, 2014, 07:00 PM
#7
Re: Expression Evaluator - Parenthesis and Negatives
Converting from the user input - in your lexical parser - into RPN format - allows for all paren issues to disappear - magic.
-
Nov 17th, 2014, 02:32 PM
#8
Re: Expression Evaluator - Parenthesis and Negatives
Sorry for getting back so late, the internet doesn't exist for me on the weekends.
I do like how the reverse polish notation takes care of the parenthesis. I will look into that to convert the normal algebraic expressions into RPN.
I've also decided to take jemidiah's response and use a lexer first to take care of my negative numbers.
Ok, after some reading. I made my way to this website. I'm following the shunting-yard algorithm, but I'm running into some issue that is not really a math question, more of a VB.Net question so what I'll do is post the question on the VB.Net forum.
-
Nov 17th, 2014, 03:22 PM
#9
Re: Expression Evaluator - Parenthesis and Negatives
Originally Posted by dday9
It allows the user to enter in an expression with however many spaces between the digits and the operators without the spacing being consistent. It follows PEMDAS, but what it does not account for is parenthesis which overrides PEMDAS and negative numbers. Right now as it sits, my code would produce a syntax error if the user attempted:
Because it would literally translate it to one plus minus one, which syntactically is invalid.
Ok, because the nerd in me is screaming... "one plus minus one, which syntactically is invalid" .. could someone please explain why? I'd interpret it (almost) the same way. one plus negative one. Or do you mean from a programmability view, it's syntactically incorrect?
-tg
-
Nov 17th, 2014, 03:24 PM
#10
Re: Expression Evaluator - Parenthesis and Negatives
As my code sat at the moment of writing that, my recursion function would recognize negative 1(-1) as minus(operator) 1. So my function was basically doing this:
Code:
1(value) +(operator) -1(value)
Would translate to:
Code:
1(value) +(operator) -(operator) 1(value)
Since then, I've done things a bit differently to allow for negatives(see my post in VB.Net forums). I'm currently in the process of recognizing to many open/closed brackets.
-
Nov 17th, 2014, 03:26 PM
#11
Re: Expression Evaluator - Parenthesis and Negatives
Ah. Ok. That makes sense.
-tg
-
Nov 17th, 2014, 04:29 PM
#12
Re: Expression Evaluator - Parenthesis and Negatives
Here's a thread from ages ago that talked on this subject
http://www.vbforums.com/showthread.p...182&viewfull=1
-
Nov 17th, 2014, 05:18 PM
#13
Re: [RESOLVED] Expression Evaluator - Parenthesis and Negatives
I was able to:
- Convert an equation represented as a string into tokens
- Parse the equation as the same time as converting the expression into RPN
- Evaluate the RPN equation
Here is the code I used:
Code:
Option Strict On
Option Explicit On
Namespace ExpressionEvaluator
Public Class Token
Public Property Name As String
Public Property Pattern As String
Public Property Precedence As Integer
Public Property Value As String
Public Function Clone(ByVal value As String) As Token
Return New Token With {.Name = Me.Name, .Pattern = Me.Pattern, .Precedence = Me.Precedence, .Value = value}
End Function
End Class
Public Class LexicalAnalyzer
Public Property Definitions As List(Of Token)
Public Property Exception As Exception
Public Property Source As String
Public Function Scan() As List(Of Token)
Dim tokens As List(Of Token) = New List(Of Token)
For Each item As String In Me.Source.Split({" "}, StringSplitOptions.RemoveEmptyEntries)
Dim found As Boolean = False
Dim regex As Text.RegularExpressions.Regex
For Each def As Token In Definitions
regex = New Text.RegularExpressions.Regex(def.Pattern)
found = regex.IsMatch(item)
If found Then
tokens.Add(def.Clone(item))
Exit For
End If
Next
If found = False Then
Me.Exception = New Exception(String.Format("Syntax Error:{0}'{1}' is not a parenthesis, operator, or valid number.", _
Environment.NewLine, item))
Return Nothing
End If
Next
Return tokens
End Function
Sub New()
Me.Definitions = New List(Of Token)
Me.Exception = Nothing
Me.Source = String.Empty
End Sub
End Class
Public Class SyntaxAnalyzer
Public Property Exception As Exception
Public Property Tokens As List(Of Token)
Public Function ConvertToRPN() As List(Of Token)
Dim conversionList As List(Of Token) = New List(Of Token)
Dim conversionStack As Stack(Of Token) = New Stack(Of Token)
For i As Integer = Me.Tokens.Count - 1 To 1 Step -1
Dim currentItem As Token = Me.Tokens(i)
Dim priorItem As Token = Me.Tokens(i - 1)
If currentItem.Name = "operators" AndAlso priorItem.Name = "operators" Then
Me.Exception = New Exception(String.Format("Syntax Error:{0}There is a double operator at: {1}{2}.", _
Environment.NewLine, currentItem.Value, priorItem.Value))
Return Nothing
End If
Next
For i As Integer = 0 To Me.Tokens.Count - 1
Dim item As Token = Me.Tokens.Item(i)
If item.Name = "digit" Then
'If the token is an operand, append it to the postfix output
conversionList.Add(item)
ElseIf item.Name = "operators" Then
'If the token(a) is an operator then...
'While there is an operator(b) of higher or equal precident than (a) at the top of the stack,
'pop (b) off the stack and append it to the output
While conversionStack.Count > 0 AndAlso conversionStack.Peek.Precedence >= item.Precedence
conversionList.Add(conversionStack.Pop)
End While
'Push (a) onto the stack
conversionStack.Push(item)
ElseIf item.Name = "lParen" Then
'If the token is an opening bracket, then push it onto the stack
conversionStack.Push(item)
Else 'If item.Name ="rParen" Then
Dim found As Boolean = False
While conversionStack.Count > 0 AndAlso found = False
If conversionStack.Peek.Name <> "lParen" Then
'Pop operators off the stack and append them to the output
conversionList.Add(conversionStack.Pop)
ElseIf conversionStack.Peek.Name = "lParen" Then
'Pop the left parentheses without adding it to the output
conversionStack.Pop()
found = True
End If
End While
'If the left parenthesis was never found then return an error
If Not found Then
Me.Exception = New Exception(String.Format("Syntax Error:{0}There are too many closed parentheses.", _
Environment.NewLine))
Return Nothing
End If
End If
Next
'When all the tokens have been read, if there are still objects in the stack:
If conversionStack.Count > 0 Then
Do
If conversionStack.Peek.Name <> "lParen" AndAlso conversionStack.Peek.Name <> "rParen" Then
'Pop the operator on the top of the stack and append it to the output
conversionList.Add(conversionStack.Pop)
Else
'There was a parentheses left, which means there were to many left parenthesis
Me.Exception = New Exception(String.Format("Syntax Error:{0}There are too many open parentheses.", _
Environment.NewLine))
Return Nothing
End If
Loop Until conversionStack.Count = 0
End If
Return conversionList
End Function
End Class
Public Class Evaluator
Public Property Tokens As List(Of Token)
Public Function EvaluateExpression() As Double
Dim valueStack As Stack(Of Token) = New Stack(Of Token)
For Each t As Token In Me.Tokens
If t.Name <> "operators" Then
valueStack.Push(t)
Else
Dim part1 As Double = Double.Parse(valueStack.Pop.Value)
Dim part2 As Double = Double.Parse(valueStack.Pop.Value)
If t.Value = "+" Then
valueStack.Push(New Token() With {.Name = "digit", .Value = (part1 + part2).ToString})
ElseIf t.Value = "-" Then
valueStack.Push(New Token() With {.Name = "digit", .Value = (part1 - part2).ToString})
ElseIf t.Value = "*" Then
valueStack.Push(New Token() With {.Name = "digit", .Value = (part1 * part2).ToString})
ElseIf t.Value = "/" Then
valueStack.Push(New Token() With {.Name = "digit", .Value = (part1 / part2).ToString})
Else 'If t.Value = "^" Then
valueStack.Push(New Token() With {.Name = "digit", .Value = (part1 ^ part2).ToString})
End If
End If
Next
Return Double.Parse(valueStack.Pop.Value)
End Function
End Class
End Namespace
And this is it being implemented:
Code:
Option Strict On
Option Explicit On
Imports ConsoleApplication1.ExpressionEvaluator
Module Module1
Sub Main()
Dim lexer As LexicalAnalyzer = New LexicalAnalyzer
lexer.Definitions = New List(Of Token) From {
{New Token() With {.Name = "lParen", .Pattern = "^(\()$", .Value = String.Empty}},
{New Token() With {.Name = "rParen", .Pattern = "^(\))$", .Value = String.Empty}},
{New Token() With {.Name = "digit", .Pattern = "^([-+]?(\d*[.])?\d+)$", .Value = String.Empty}},
{New Token() With {.Name = "operators", .Pattern = "^(\+|-)$", .Precedence = 1, .Value = String.Empty}},
{New Token() With {.Name = "operators", .Pattern = "^(\*|/)$", .Precedence = 2, .Value = String.Empty}},
{New Token() With {.Name = "operators", .Pattern = "^(\^)$", .Precedence = 3, .Value = String.Empty}}}
lexer.Source = Console.ReadLine
Dim tokens As List(Of Token) = lexer.Scan
If tokens IsNot Nothing Then
Dim parser As SyntaxAnalyzer = New SyntaxAnalyzer With {.Tokens = tokens}
Dim rpn As List(Of Token) = parser.ConvertToRPN
If rpn IsNot Nothing Then
Dim solver As Evaluator = New Evaluator With {.Tokens = rpn}
Console.WriteLine(solver.EvaluateExpression.ToString)
Else
Console.WriteLine()
Console.WriteLine(parser.Exception.Message)
End If
Else
Console.WriteLine()
Console.WriteLine(lexer.Exception.Message)
End If
Console.ReadLine()
End Sub
End Module
The only thing I'm unhappy with is that it requires a space between everything. So this:
Would have to be written as:
-
Nov 17th, 2014, 05:20 PM
#14
Re: [RESOLVED] Expression Evaluator - Parenthesis and Negatives
So now go nuts with operators.
Then start doing functions like Left("xyz",1)
and a really cool one: If(cond, val1, val2)
-
Nov 17th, 2014, 05:22 PM
#15
Re: [RESOLVED] Expression Evaluator - Parenthesis and Negatives
Originally Posted by szlamany
So now go nuts with operators.
Then start doing functions like Left("xyz",1)
and a really cool one: If(cond, val1, val2)
That's the plan, but man this is much harder than I thought.
-
Nov 17th, 2014, 05:25 PM
#16
Re: [RESOLVED] Expression Evaluator - Parenthesis and Negatives
One of the files in that link I gave back in post #12 shows all the operators we allowed in our old VAX database system. I can remember when we came up with the SIGMA() function...
Scroll this list down till you get past PRECEDENCE ZERO...
Code:
EQU operations
Operator Precedence Function
-------------- ---------- ----------------------------------------------
CNV_NAM(P$,N$) 0 Converts the data base field name N$ in the file
whose prefix is P$ into a field number
CHK_FIL(P$) 0 Checks the data base prefix P$ to see if it
is valid. If it is not it returns -1%.
CHK_FLD(P$,N%) 0 Checks the data base field number N% in the file
whose prefix is P$ to see if it is valid. If
it is not it returns an error number.
CHK_NAM(P$,N$) 0 Checks the data base field name N$ in the file
whose prefix is P$ to see if it is valid. If
it is not it returns an error number.
EDIT$(A$,B%) 0 Converts A$ according to B%
ERT(A) 0 Returns error text for BASIC/DBD error number A
FORMAT$(A,B$) 0 Format the numeric A using B$.
GETFLD(P$,F%,F$) 0 Returns the contents of the database field
given by the prefix P$ and the field number
F% and in the format F$. F$ may be either
"DSP", "STO" or "INP".
IF(A,B,C) 0 Return B if A is true else return C.
LEFT(A$,A) 0 Extract the leftmost A characters of A$.
MID(A$,A,B) 0 Extract Characters A through A+B-1 from
the string A$.
PLACE$(A,B) 0 Round A to B decimal places.
POS(A$,B$,C) 0 Search for B$ within A$ starting at C. Return
the position of B$ within A$ or zero if not
found.
RIGHT(A$,A) 0 Extract the rightmost A characters of A$.
SEG$(A$,B,C) 0 Return characters B though C of A$.
SIGMA(C,I,T,S,E) 0 Return the summation of the expression E
for C = I to T step S
UIC() 0 Returns the current process UIC in the form
[GGG,PPP].
USERNAME() 0 Returns the current process user name.
VAL_ERR(A$) 0 Returns true if A$ not a number
TRANS_DATE(I$,O$,D$) 0 Converts D$ from date format I$ into date
format O$.
TABLE(P$,I$,C$,E%) 0 Returns the table element found in the .TBS
whose prefix is given by P$, and whose table
identifier is given by I$ and whose key is
given by C$ and whse element number is E%.
A ^ B% 1 Exponentiation
- A 2 Unary Minus
+ A 2 Unary Plus
A * B 3 Multiplication
A / B 3 Division
A + B 4 Addition
A - B 4 Subtraction
A$ | B$ 5 Concatenation
EQU operations
Operator Precedence Function
-------------- ---------- ----------------------------------------------
A < B 6 A less than B (numeric).
A = B 6 A equal to B (numeric).
A > B 6 A greater than B (numeric).
A <= B 6 A Less than or equal to B (numeric).
A >= B 6 A greater than or equal to B (numeric).
A <> B 6 A not equal to B (numeric).
A$ << B$ 6 A$ less than B$ (string).
A$ == B$ 6 A$ equal to B$ (string).
A$ >> B$ 6 A$ greater than B$ (string).
A$ <<== B$ 6 A$ less than or equal to B$ (string).
A$ >>== B$ 6 A$ greater than or eqal to B$ (string).
A$ <<>> B$ 6 A$ not equal to B$ (string).
NOT A% 7 Ones complement of A% .
A% AND B% 8 The logical product of A% and B%.
A% OR B% 9 The logical addition of A% and B%.
A% XOR B% 9 The logical exclusive OR of A% and B%.
A% IMP B% 10 The logical implication of A% and B%.
A% EQV B% 11 The logical equivalence of A% and B%.
Last edited by szlamany; Nov 17th, 2014 at 06:27 PM.
-
Nov 17th, 2014, 11:08 PM
#17
Re: [RESOLVED] Expression Evaluator - Parenthesis and Negatives
I had a more iterative approach in mind for the lexer. That is, you run through the code character by character adding tokens to a queue as you go. It's fundamentally similar to what you're doing, but it'd be more flexible than splitting at spaces and using regex's to try and figure out what happened. For instance, for "1 + -1", I'd read "1" and enter "number lexing mode". I'd probably just strip whitespace beforehand, so I wouldn't even read " ". I'd then read "+" and end "number lexing mode", so I'd add "1" to the queue. I'd also enter "operator lexing mode", then read "-" and, since I'm in operator lexing mode, I'd know this must mean unary negation rather than binary subtraction. Hence I'd add "+" to the queue and enter "number lexing mode". I'd read 1, stay in number lexing mode, hit EOF, and add "-1" to the queue.
Anywho, this whole thing illustrates the wonders of a modular approach here. You can completely redo the lexer without affecting the parser.
The time you enjoy wasting is not wasted time.
Bertrand Russell
<- Remember to rate posts you find helpful.
-
Nov 19th, 2014, 11:27 AM
#18
Re: [RESOLVED] Expression Evaluator - Parenthesis and Negatives
Just an update as well. I had noticed that for whatever reason I was getting wrong answers with the following equations:
Code:
1 - 15
'Returned 14
Code:
15 - 1
'Returned -14
The issue was I had the part1 and part2 backwards in the EvaluateExpression function. So I just swapped it.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|