0
\$\begingroup\$

I have implemented a "infix-to-postfix" function that takes as input a list representing the parsed expression, resulted from applying a certain regular expression to an expression, and I would like to have your opinion regarding its correctness and efficiency. Good suggestions are of course more than well-accepted!

For making you able also to test directly my algorithm, I decided to include also the regular expression and other important details.

import re


# higher number => higher precedence
OPERATORS  = {
    "+": 1,
    "-": 1,
    "*": 2,
    "/": 2,
    "%": 2,
    "^": 3
}

PARENTHESIS = set(["(", ")"])

REGEX = "(\d+|\w+|[()\-+*/^%])"


def parse(e):
    """Parses a string expression e to a infix represation list."""
    return re.findall(REGEX, e)


def infix_to_postfix(infix):
    stack = []
    postfix = []

    for c in infix:
        if c in OPERATORS:

            if len(stack) > 0:                
                top = stack[-1]

                if top in OPERATORS.keys():
                    if OPERATORS[c] > OPERATORS[top]:
                        stack.append(c)
                    else:
                        while top in OPERATORS.keys() and OPERATORS[top] >= OPERATORS[c]:
                            op = stack.pop()
                            postfix.append(op)

                            if len(stack) > 0:
                                top = stack[-1]
                            else:
                                break
                        stack.append(c)
                else:
                    stack.append(c)
            else:
                stack.append(c)

        elif c in PARENTHESIS:

            if c == ")":
                if len(stack) > 0:
                    top = stack[-1]

                    while top != "(":
                        try:
                            # pop throws an IndexError if the list is empty
                            r = stack.pop()
                            postfix.append(r)  # Adding what's in between ( ) to the postfix list
                            top = stack[-1]
                        except IndexError:
                            raise ValueError("'(' not found when popping")

                    stack.pop()  # Removes ( from the top of the stack
                else:
                    raise ValueError("')' cannot be added to the stack if it is empty") 
            else:
                stack.append(c)  # c == '('
        else:

            postfix.append(c)

        #print("Stack:", stack)
        #print("Postfix:", postfix)

    while len(stack) > 0:
        top = stack.pop()

        if top in OPERATORS.keys():
            postfix.append(top)

    return postfix

Please, don't tell me anything about the docstrings, because I actually removed them from my code to make it clearer.

In general, I prefer efficiency to clarity, so I am not so interested in list or generator comprehensions if they don't make the code more efficient. Anyway, you could also suggest them, if you feel that they would turn the code more "pythonic".

\$\endgroup\$
2
\$\begingroup\$

The first thing I notice is the deep nesting in infix_to_postfix. Deep nesting like that is generally undesirable. We'll get to that later.

Second, for the parenthesis, my instinct would be to say: "Use frozenset instead of set.". But after some benchmarking: set is actually fastest on my machine, so probably also on yours. (I also checked using a tuple instead, again slower than using a set). However, a more Pythonic declaration of the set would be PARENTHESIS = {"(", ")"}.

Regarding the regular expression and the method parse: it could be faster by using a compiled regex instead of using re.findall. Also, convention has it that you use raw strings for regular expressions.

REGEX = re.compile(r"(\d+|\w+|[-+*/^%()])")
def parse(e, REGEX=REGEX):
    return REGEX.findall(e)

The REGEX=REGEX trick is an optimization trick preventing a lookup to the global dictionary. Using compiled regular expressions also gains a bit of speed. (On the other hand: I don't see parse being used, so that's probably ok).

Since it's not documented, I'm going to assume the calling convention will be

postfix_tokens = infix_to_postfix(parse(infix_tokens)

Now, let's start analysing the large method infix_to_postfix. First of all, we could apply the same trick as we did for REGEX to speed up the lookup for OPERATORS. That's going to make your code a bit more efficient.

It's a tad large, so let's first talk about the if c in OPERATORS branch.

if len(stack) > 0:
    top = stack[-1]

    if top in OPERATORS.keys():
        if OPERATORS[c] > OPERATORS[top]:
            stack.append(c)
        else:
            while top in OPERATORS.keys() and OPERATORS[top] >= OPERATORS[c]:
                op = stack.pop()
                postfix.append(op)

                if len(stack) > 0:
                    top = stack[-1]
                else:
                    break
            stack.append(c)
    else:
        stack.append(c)
else:
    stack.append(c)

All these else conditions look the same. Let's see if we can simplify it a bit. Let's start by flipping the if and else branch in if OPERATORS[c] > OPERATORS[top]. (> becomes <=).

if len(stack) > 0:
    top = stack[-1]

    if top in OPERATORS.keys():
        if OPERATORS[c] <= OPERATORS[top]:
            while top in OPERATORS.keys() and OPERATORS[top] >= OPERATORS[c]:
                op = stack.pop()
                postfix.append(op)

                if len(stack) > 0:
                    top = stack[-1]
                else:
                    break
            stack.append(c)
        else:
            stack.append(c)
    else:
        stack.append(c)
else:
    stack.append(c)

Now, we have the following construct:

if cond:
    A()
    B()
 else:
    B()

Which we can rewrite to

if cond:
    A()
 B()

Applying that several times we get

if len(stack) > 0:
    top = stack[-1]

    if top in OPERATORS.keys():
        if OPERATORS[c] <= OPERATORS[top]:
            while top in OPERATORS.keys() and OPERATORS[top] >= OPERATORS[c]:
                op = stack.pop()
                postfix.append(op)

                if len(stack) > 0:
                    top = stack[-1]
                else:
                    break

stack.append(c)

Wow, we saved a few lines of code. If we're lucky, it's also going to gain us some performance.

Next, you have top in OPERATORS.keys(). This can be replaced by top in OPERATORS (as that's how dict containment checking works). Furthermore, len(stack) > 0 can be replaced by stack.

Furthermore, you write op = stack.pop() followed by postfix.append(op). You can simplify this to postfix.append(stack.pop()).

if stack:
    top = stack[-1]

    if top in OPERATORS:
        if OPERATORS[c] <= OPERATORS[top]:
            while top in OPERATORS and OPERATORS[top] >= OPERATORS[c]:
                postfix.append(stack.pop())

                if stack > 0:
                    top = stack[-1]
                else:
                    break

stack.append(c)

Let's continue our focus on the nested if top in OPERATORS. Now, for symmetry, we replace OPERATORS[c] <= OPERATORS[top] with OPERATORS[TOP] >= OPERATORS[C]. (I'm not showing the if stack: and stack.append(c) anymore).

if top in OPERATORS:
    if OPERATORS[top] >= OPERATORS[c]:
        while top in OPERATORS and OPERATORS[top] >= OPERATORS[c]:
            postfix.append(stack.pop())

            if stack > 0:
                top = stack[-1]
            else:
                break

We can merge the first two conditionals, because there are no else branches, using

if cond_a:
    if cond_b:
        ...

to

if cond_a and cond_b:
    ...

We get

if top in OPERATORS and OPERATORS[top] >= OPERATORS[c]:
    while top in OPERATORS and OPERATORS[top] >= OPERATORS[c]:
        postfix.append(stack.pop())

        if stack > 0:
            top = stack[-1]
        else:
            break

Now the similarity should be obvious, we can drop the if.

Zooming out again:

def infix_to_postfix(infix):
    stack = []
    postfix = []

    for c in infix:
        if c in OPERATORS:

            if stack:
                top = stack[-1]

                while top in OPERATORS and OPERATORS[top] >= OPERATORS[c]:
                    postfix.append(stack.pop())

                    if stack:
                        top = stack[-1]
                    else:
                        break

            stack.append(c)

        elif c in PARENTHESIS:

            if c == ")":
                if len(stack) > 0:
                    top = stack[-1]

                    while top != "(":
                        try:
                            # pop throws an IndexError if the list is empty
                            r = stack.pop()
                            postfix.append(r)  # Adding what's in between ( ) to the postfix list
                            top = stack[-1]
                        except IndexError:
                            raise ValueError("'(' not found when popping")

                    stack.pop()  # Removes ( from the top of the stack
                else:
                    raise ValueError("')' cannot be added to the stack if it is empty") 
            else:
                stack.append(c)  # c == '('
        else:

            postfix.append(c)

        #print("Stack:", stack)
        #print("Postfix:", postfix)

    while len(stack) > 0:
        top = stack.pop()

        if top in OPERATORS.keys():
            postfix.append(top)

    return postfix

The first branch of the conditional is cleaned up nicely. Let's consider the second branch, most specifically the handling of ")".

You're checking if len(stack) > 0, and throwing a ValueError otherwise because of an empty stack. What you actually mean is "')' cannot be added to the stack if there is no '(' in the stack". That's already checked by the other branch, so this condition is superfluous. However, we can't just remove it just yet, because top = stack[-1] might then throw an IndexError. So, let's continue and see if we get another opportunity to fix it later.

In the while loop, we see a try/except. The except has a raise, so we might as well move it outside the loop. (I took the liberty to also remove the temporary variable r).

top = stack[-1]
try:
    while top != "(":
        postfix.append(stack.pop())
        top = stack[-1]
except IndexError:
    raise ValueError("'(' not found when popping")

stack.pop()  # Removes the ( from the top of the stack

Looking at efficiency: you're storing stack[-1] in a temporary variable, and then loading it again for the while condition. We can fix that

try:
    while stack[-1] != "(":
        postfix.append(stack.pop())
except IndexError:
    raise ValueError("'(' not found when popping")

stack.pop()  # Removes the ( from the top of the stack

Remember the if we wanted to remove? We can actually do that now!

        ...
        elif c in PARENTHESIS:

            if c == ")":
                try:
                    while stack[-1] != "(":
                        postfix.append(stack.pop())
                except IndexError:
                    raise ValueError("'(' not found when popping")

                stack.pop()  # Removes ( from the top of the stack
            else:
                stack.append(c)  # c == '('
        else:
            ...

The code is now shaping up nicely. Let's consider the final while loop. Here you're poping until it's empty. Why not just loop over it in reverse? (The stack is going to be destructed anyway). Iteration is probably cheaper than mutation.

    for token in reversed(stack):
        if token in OPERATORS.keys():
            postfix.append(token)

In fact, it would probably be more efficient to use a generator comprehension here.

     postfix.extend(token for token in reversed(stack) if token in OPERATORS)

In the end, we end up with

def infix_to_postfix(infix):
    stack = []
    postfix = []

    for c in infix:
        if c in OPERATORS:

            if stack:
                top = stack[-1]

                while top in OPERATORS and OPERATORS[top] >= OPERATORS[c]:
                    postfix.append(stack.pop())

                    if stack:
                        top = stack[-1]
                    else:
                        break

            stack.append(c)

        elif c in PARENTHESIS:

            if c == ")":
                try:
                    while stack[-1] != "(":
                        postfix.append(stack.pop())
                except IndexError:
                    raise ValueError("'(' not found when popping")

                stack.pop()  # Removes ( from the top of the stack
            else:
                stack.append(c)  # c == '('
        else:

            postfix.append(c)

        #print("Stack:", stack)
        #print("Postfix:", postfix)

    postfix.extend(token for token in reversed(stack) if token in OPERATORS)

    return postfix

And we can probably shave some extra lines off it even more, but I don't think that's necessary because now it is a bit more understandable.

As for the points @GarethRees mentioned: those should also be taken care of, as it does not make much sense like this. Probably best to ask for a new code-review after you made these changes.

\$\endgroup\$
  • \$\begingroup\$ I forgot: a good thing to look up is the Shunting Yard algorithm by Edsger W. Dijkstra. \$\endgroup\$ – Sjoerd Job Postmus Jan 16 '16 at 21:15
  • \$\begingroup\$ Thanks for the tips! I am not if I will adopt them all, but some for sure. Now I have provided some logic/code to handle the cases mentioned by @GarethRees... As you are suggesting, maybe later I will post another question with the updated code. \$\endgroup\$ – nbro Jan 16 '16 at 22:46
1
\$\begingroup\$

This code doesn't detect syntax errors in the expression. It accepts two numbers with no operator:

>>> infix_to_postfix(['1', '2'])
['1', '2']

It accepts two operators with no number:

>>> infix_to_postfix(['+', '*'])
['*', '+']

It accepts unbalanced parentheses:

>>> infix_to_postfix(['(', '('])
[]

These cases should all be rejected as syntax errors.

\$\endgroup\$
  • \$\begingroup\$ I didn't detect those cases because Python already detects them if you write the expression first as a string (I was working with strings that are converted to lists), i.e. it doesn't run the unbalanced string expression (for example), and I wanted to disable that option... actually I don't know why it was doing that, since it's simply a string. But thanks for pointing those problems out. \$\endgroup\$ – nbro Jan 16 '16 at 16:56
  • \$\begingroup\$ There are also other syntax errors that my parser doesn't detect, for example if you have 2 operators in a row...Probably I should try to fix all of them. Do you think that I should detect all theses errors together in my function, or I should maybe separate the tasks of detecting different errors? \$\endgroup\$ – nbro Jan 16 '16 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.