Adding Infix to Postfix Conversion to SymPy

[JDKelly]

Dear Ondrej;

Here is the Python code I am using to do infix-to-posfix conversions
which I modified to add ln(), exp(), sin() functions from Premshree
Pillai but I currently do not have unary minus supported.

I would like this to be added as a core feature of say SymPy which
seems to me the most logical place for it.

Best Regards, Jeff

###############################################################################
# Infix-to-Postfix Conversion
#################################################
###############################################################################

# The following functions are used to convert from infix to # postfix
or reverse Polish notation (RPN) for property-transforms, # property-
properties, condition-densities, condition-components and # condition-
properties, etc.
#
# These support unary minus and unary operators such as exp() and
sin().
#
# First, the infix string is converted to a tokenized list of operands
and # operators still in infix form. Then this tokenized list is
converted # to a list in postfix form.
#
# * IMPORTANT NOTE:
#
# At the moment, we do NOT support "unary minus". It may be more
# efficient to handle this during the evaluation stage when the
# number stack is empty but an unary-minus is found then we
# can retrieve the previous value in the stack and return the
# negative of it.
#
# References:
#
# Premshree Pillai, "infix-postfix.py" (Python), http://www.qiksearch.com,
July, 2003.
#
# This Python code was converted to Fortran code where in Python
"stacks"
# or "queues" are easily implemented using "lists". Instead, the
stack was
# implemented using a Fortran character string or character array
with pop and push
# operations implemented using an explicit stackptr to the
stack.
#
# However, this code only implmented binary operators of
"+","-","*","/" and "^"
# and has been extended to include unary operators i.e., abs,
sign, log, log10,
# exp, sin, cos, tan, asin, acos, atan, etc. as well as in-line
comments are
# added which were absent in the original Python code. It also
handles a
# conversion to lower-case ASCII characters.
#
# Erik Oosterwal, "Infix to RPN" (Visual Basic 6.0), November,
2005.
#
# This VB6 code was first converted to Xpress-Mosel. However,
migration to
# Fortran was not performed. This program was used a reference
only.
#
# It was implemented in Xpress-Mosel for NCDARRS.MOS
(NCDARRB.MOS) but it was found
# to be difficult to extend or enhance to allow user-defined-
functions.

def push_stack(stack,x):
stack.append(x)
def pop_stack(stack):
return stack.pop()
def top_stack(stack):
return(stack[len(stack)-1])
def is_empty(stack):
if(len(stack) == 0):
return 1
return 0
def is_unaryoperator(x):
if (x.lower() == "sqrt" or \
x.lower() == "exp" or \
x.lower() == "ln" or \
x.lower() == "log" or \
x.lower() == "sin" or \
x.lower() == "cos" or \
x.lower() == "tan" or \
x.lower() == "arcsin" or \
x.lower() == "arccos" or \
x.lower() == "arctan"):
return 1
return 0
def is_binaryoperator(x):
if (x == "+" or \
x == "-" or \
x == "*" or \
x == "/" or \
x == "^"):
return 1
return 0
def is_operand(x):
if (not(is_unaryoperator(x)) and \
not(is_binaryoperator(x)) and \
x != "(" and \
x != ")"):
return 1
return 0
def precedence(x):
if(x == "^"):
return(5)
if((x == "*") or (x == "/")):
return(4)
if((x == "+") or (x == "-")):
return(3)
if(x == "("):
return(2)
if(x == ")"):
return(1)
def infix2tokens(infixStr):
tempStr = ""
tokensStr = []
count = 0
for x in infixStr:
count += 1
if x != " ":
if(is_operand(x)):
tempStr += x
if(is_binaryoperator(x) or \
x == ")" or x == "("):
if(tempStr != ""):
tokensStr.append(tempStr)
tempStr = ""
tokensStr.append(x)
if(count == len(infixStr)):
if(tempStr != ""):
tokensStr.append(tempStr)
return(tokensStr)
def tokens2postfix(tokensStr,postfixStr = []):
stack = []
postfixStr = []
for x in tokensStr:
if(is_operand(x)):
postfixStr.append(x)
if(is_unaryoperator(x)):
push_stack(stack,x)
if(is_binaryoperator(x)):
if(x != "^"):
while((not(is_empty(stack))) and \
(precedence(x) <= precedence(top_stack(stack)))):
postfixStr.append(top_stack(stack))
pop_stack(stack)
else:
while((not(is_empty(stack))) and \
(precedence(x) < precedence(top_stack(stack)))):
postfixStr.append(top_stack(stack))
pop_stack(stack)
push_stack(stack,x)
if(x == "("):
push_stack(stack,x)
if(x == ")"):
while(top_stack(stack) != "("):
postfixStr.append(pop_stack(stack))
pop_stack(stack)
if not(is_empty(stack)):
if (is_unaryoperator(top_stack(stack))):
postfixStr.append(pop_stack(stack))
while(not(is_empty(stack))):
if(top_stack(stack) == "("):
pop_stack(stack)
else:
postfixStr.append(pop_stack(stack))
return(postfixStr)

[Ondrej Certik]

Hi Jeff!

On Thu, Sep 18, 2008 at 2:25 PM, JDKelly <jeffreyd...@gmail.com> wrote:
>
> Dear Ondrej;
>
> Here is the Python code I am using to do infix-to-posfix conversions
> which I modified to add ln(), exp(), sin() functions from Premshree
> Pillai but I currently do not have unary minus supported.
>
> I would like this to be added as a core feature of say SymPy which
> seems to me the most logical place for it.

Thanks a lot for the code, it would be very nice if sympy could do
that. I created an issue for it:

http://code.google.com/p/sympy/issues/detail?id=1110

Would you like to fix it? :) I.e. as I wrote in the issue, someone now
needs to polish it, write tests and prepare a patch for the inclusion.

Thanks,
Ondrej

[JDKelly]

Ondrej;

I have added some more to text to the issue in terms of the
specification of an infix-to-postfix conversion.

I hope this is what you were asking for.

Best Regards, Jeff

On Sep 18, 9:39 am, "Ondrej Certik" <ond...@certik.cz> wrote:
> Hi Jeff!
>

[Ondrej Certik]

On Fri, Sep 19, 2008 at 12:00 PM, JDKelly <jeffreyd...@gmail.com> wrote:
>
> Ondrej;
>
> I have added some more to text to the issue in terms of the
> specification of an infix-to-postfix conversion.
>
> I hope this is what you were asking for.

Thanks, that's very useful indeed.

Now someone (you?) needs to find time to actually produce a patch
based on your patch and the specification you wrote. Unfortunately, I
cannot do it now, learning for my master finals.

Ondrej

[Ondrej Certik]

On Fri, Sep 19, 2008 at 12:18 PM, Ondrej Certik <ond...@certik.cz> wrote:
> On Fri, Sep 19, 2008 at 12:00 PM, JDKelly <jeffreyd...@gmail.com> wrote:
>>
>> Ondrej;
>>
>> I have added some more to text to the issue in terms of the
>> specification of an infix-to-postfix conversion.
>>
>> I hope this is what you were asking for.
>
> Thanks, that's very useful indeed.
>
> Now someone (you?) needs to find time to actually produce a patch
> based on your patch and the specification you wrote. Unfortunately, I

based on your code.

O.

[Jeffrey Dean Kelly]

Ondrej;

 

How would I go about doing this?

 

My code handles everyting except unary-minus and user-defined Python functions we can add later.

 

Best Regards, Jeff

[Ondrej Certik]

On Fri, Sep 19, 2008 at 12:49 PM, Jeffrey Dean Kelly
<jeffreyd...@gmail.com> wrote:
> Ondrej;
>
> How would I go about doing this?
>
> My code handles everyting except unary-minus and user-defined Python
> functions we can add later.

Yes, you need to decide where in sympy it should live and produce a
patch. If you use mercurial, follow our tutorial:

http://docs.sympy.org/sympy-patches-tutorial.html

if you use git, just produce the patch using git:

http://git.sympy.org/

if you use neither, I think it's a good idea to learn one, it will be
useful for you in the future.

Ondrej