8
\$\begingroup\$

I was trying to implement an efficient (in terms of size of code (such as using one liners) and time and memory-efficient) of Infix to Postfix in python without the use of any external modules i.e using only inbuilt modules and with only necessary addition (such as without class to implement stack probably not needed).

Currently, my code looks like the following

operators={"+":1,"-":1,"*":2,"/":2,"^":3,"**":3,"(":4,")":4}

def InfixtoList(Infix):
    NewInfix,tmp=[],""
    for i in Infix:
        if  i.isdigit() or i.isalpha():tmp+=i
        else:NewInfix,tmp=NewInfix+([tmp,i] if tmp else [i]),""
    NewInfix.append(tmp)
    return NewInfix

def InfixToPostfix(infix):
    answer,stack=[],[]
    infix=InfixtoList(infix)
    for i in infix:
        print(i,infix)
        if i.isdigit() or i.isalpha():answer.append(i)
        elif i=="(":stack.append(i)
        elif i==")":
            while stack!=[] and stack[-1]!="(":answer.append(stack.pop())
        else:
            while stack!=[] and operators[i]<=operators[stack[-1]]:answer.append(stack.pop()) 
            stack.append(i)
    while stack!=[]:answer.append(stack.pop())
    return "".join(answer).replace("(","")

Currently, it uses Shunting-yard algorithm i.e using stacks, without support for functions.

The function InfixtoList separates the operands and operators and put them in a list. The Code above works both for operands as digits or alphabet.

I am currently trying to make a better implementation of converting postfix to infix preferably using the same algorithm.

\$\endgroup\$
0
5
\$\begingroup\$

I was trying to implement an efficient (in terms of size of code and time and memory-efficient) of Infix to Postfix in python without the use of any modules and with only necessary parts (such as without class).

First of all, there is nothing intrinsically bad about classes. You should feel free to decide between object based programming or not based on the problem and your preferences. And I don't understand quite what you mean by "not using modules" - you're using lists and strings and all other types of Python standard library data models and functions.

Efficiency

There's a saying by Donald Knuth that "about 97% of the time: premature optimization is the root of all evil." You should generally only attempt to optimise something once its performance impacts you (and you can quantify this!). And when you talk about optimisation, you also have to understand that there are trade-offs; optimising for speed/cycles will often mean that the algorithm requires more memory, and vice versa. I'd also argue that if you don't know the time and space complexity of your function you're not ready to optimise. It's also good to recognise that you optimise within a context - doing something in pure Python is only ever going to be so fast (Python is a high-level language with a lot of overhead).

Now, you also mention optimising for "size of code". This is not a good idea. Your script is currently 820 bytes. By shortening your indendations and your variable and function names I can get it down to 542 bytes (or less if I had the energy):

op={"+":1,"-":1,"*":2,"/":2,"^":3,"**":3,"(":4,")":4}
def itl(ix):
 nix,t=[],""
 for i in ix:
  if i.isdigit() or i.isalpha():t+=i
  else:nix,t=nix+([t,i] if t else [i]),""
 nix.append(t)
 return nix
def itpx(ix):
 a,s=[],[]
 ix=itl(ix)
 for i in ix:
  print(i,ix)
  if i.isdigit() or i.isalpha():a.append(i)
  elif i=="(":s.append(i)
  elif i==")":
   while s!=[] and s[-1]!="(":a.append(s.pop())
  else:
   while s!=[] and op[i]<=op[s[-1]]:a.append(s.pop())
   s.append(i)
 while s!=[]:a.append(s.pop())
 return "".join(a).replace("(","")

Is this code better? I think you would agree that it isn't. You typically don't have to care about the length of your scripts - some hundred or even 10's of thousands of bytes are not going to matter on a modern computer. And if it did, you surely wouldn't be using Python. But there are a few things that we value very highly in the Python community, which you can summon in the interpreter:

$ python3 -i
Python 3.7.6 (default, Jan  8 2020, 19:59:22)
[GCC 7.3.0] :: Anaconda, Inc. on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import this
The Zen of Python, by Tim Peters

Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
Flat is better than nested.
Sparse is better than dense.
Readability counts.
Special cases aren't special enough to break the rules.
Although practicality beats purity.
Errors should never pass silently.
Unless explicitly silenced.
In the face of ambiguity, refuse the temptation to guess.
There should be one-- and preferably only one --obvious way to do it.
Although that way may not be obvious at first unless you're Dutch.
Now is better than never.
Although never is often better than *right* now.
If the implementation is hard to explain, it's a bad idea.
If the implementation is easy to explain, it may be a good idea.
Namespaces are one honking great idea -- let's do more of those!

Now, from this text you may be able to infer that we value readability and simplicity in Python. So what consistutes a good function or script is generally by how easily understandable it is. That brings us to the feedback area.

Conventions and expectations

If I read Python code, I assume that the author is following PEP8 or some other established style convention (e.g. uses black). This typically means that constant (global) variables are uppercase, classes are PascalCase, variables are snake_case, and verbosity is almost exaggerated to guarantee that the code is easily understandable. Your code would look something like this:

from typing import List

OPERATOR_PRIORITY = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3, "**": 3, "(": 4, ")": 4}


def separate_infixes(equation: str) -> List[str]:
    infixes, tmp = [], ""
    for symbol in equation:
        if symbol.isdigit() or symbol.isalpha():
            tmp += symbol
        else:
            infixes, tmp = infixes + ([tmp, symbol] if tmp else [symbol]), ""
    infixes.append(tmp)
    return infixes


def convert_infix_to_postfix(equation: str) -> str:
    answer, stack = [], []
    infixes = separate_infixes(equation)
    for symbol in infixes:
        print(symbol, infixes)
        if symbol.isdigit() or symbol.isalpha():
            answer.append(symbol)
        elif symbol == "(":
            stack.append(symbol)
        elif symbol == ")":
            while stack != [] and stack[-1] != "(":
                answer.append(stack.pop())
        else:
            while (
                stack != []
                and OPERATOR_PRIORITY[symbol] <= OPERATOR_PRIORITY[stack[-1]]
            ):
                answer.append(stack.pop())
            stack.append(symbol)
    while stack != []:
        answer.append(stack.pop())
    return "".join(answer).replace("(", "")

Now I think (hope?) you will agree that this is far more easily readable than the "length-optimised" version.

Readability counts.

Always remember those words - they are, at least in my opinion, the most important part of the Zen of Python (aka PEP20). Write your code with a future reader in mind, because that reader will most of the time be yourself, and you will all too often stop to wonder what the idiotic author (who generally is yourself) had in mind when they wrote something up. Be overly clear with names, and use comments as well as docstrings.

Other small bits

if i.isdigit() or i.isalpha(): tmp+=i

Although it's not exactly the same check, you can use str.isalnum().

while stack!=[]:answer.append(stack.pop())

Instead of checking if stack != [] you can just check if stack.

print(i,infix)

This looks like a "debugging print", i.e. something you used as an aide during development but which shouldn't be part of the function. You may want to get used to using a debugger in the future.


Now, with all of this done - as well as making the split-function internal just for good grace - we've ended up with something closer to:

from typing import List

OPERATOR_PRIORITY = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3, "**": 3, "(": 4, ")": 4}


def convert_infix_to_postfix(equation: str) -> str:
    """Converts infix to postfix.

    For example:
      for infix expression x^y/(5*z)+2
      the postfix form is xy^5/z*2+

    Considers the operators: +, -, *, /, ^, **, (, and )
    """
    def separate_symbols(string: str) -> List[str]:
        """Helper method."""
        symbols = []
        tmp = ""
        for char in string:
            if char.isalnum():
                # store variables and digits in a string
                tmp += char
            else:
                symbols = symbols + ([tmp, char] if tmp else [char])
                tmp = ""
        symbols.append(tmp)
        return symbols

    solution, stack = [], []
    for symbol in separate_symbols(equation):
        if symbol.isalnum() or symbol == "(":
            solution.append(symbol)
        elif symbol == ")":
            while stack and not stack[-1] == "(":
                solution.append(stack.pop())
        else:
            while stack and OPERATOR_PRIORITY[symbol] <= OPERATOR_PRIORITY[stack[-1]]:
                solution.append(stack.pop())
            stack.append(symbol)
    solution += stack
    return "".join(solution).replace("(", "")

There's still a tonne of improvements that can be made, but I hope I've managed to give you at least something to work based off. Now I don't feel like I have more time to spend on this, but the next two improvements that I'd personally look towards if I were you would be to add some basic tests, and to add docstrings that explain what the functions do, and maybe even add some examples.

\$\endgroup\$
4
  • \$\begingroup\$ @FMc - I just searched for an infix to postfix function on google and took an arbitrary equation, which I arguably shouldn't have done. I don't, however, get any KeyError, but I do get the wrong results (even if they are consistent with the original script - xy^5/z*2+); can you show me where you get the KeyError? \$\endgroup\$
    – ades
    Jan 10 at 16:23
  • \$\begingroup\$ The main reason I mentioned avoiding the use of classes was that I do not think they are needed here just to create a stack object but they do come useful in certain conditions. by not using any modules I meant not importing external modules however I should have mentioned in the description. I think both time and space complexity are O(n) which probably cannot be changed however I think maybe there are better implementations that are more pythonic such uses one-liners \$\endgroup\$ Jan 10 at 18:53
  • \$\begingroup\$ . This answer and the previous answer by Greedo seem to be focused on readability and style which did not think of but it is necessary. I will add a basic test and output case after some time. \$\endgroup\$ Jan 10 at 18:54
  • 2
    \$\begingroup\$ Good code typically avoids one-liners unless they are for trivial operations, or otherwise just are easily understandable. Some of the examples in your link (f = lambda x: [[y for j, y in enumerate(set(x)) if (i >> j) & 1] for i in range(2**len(set(x)))]) are text-book examples of bad code. There are probably good list comprehensions that could be used over your implementation, but that's not what you should focus on, in my opinion. \$\endgroup\$
    – ades
    Jan 10 at 18:58
3
\$\begingroup\$

Quick improvement*: put your code through an automatic formatter. Python has a guideline called PEP8 which gives recommendations on where to put linebreaks, spaces, how to name things consistently. I use black to format code since it is PEP8 compliant and does all the decision making for you so you can focus on more important things (it doesn't do everything - for example it won't change the names of your variables despite PEP8 having recommendations for even this).

Formatting code consistently makes it more readable (and thus maintainable) for you, and following a conventional approach like PEP8 makes it more readable for everyone else.

Formatting with black results in this:

operators = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3, "**": 3, "(": 4, ")": 4}


def InfixtoList(Infix):
    NewInfix, tmp = [], ""
    for i in Infix:
        if i.isdigit() or i.isalpha():
            tmp += i
        else:
            NewInfix, tmp = NewInfix + ([tmp, i] if tmp else [i]), ""
    NewInfix.append(tmp)
    return NewInfix


def InfixToPostfix(infix):
    answer, stack = [], []
    infix = InfixtoList(infix)
    for i in infix:
        print(i, infix)
        if i.isdigit() or i.isalpha():
            answer.append(i)
        elif i == "(":
            stack.append(i)
        elif i == ")":
            while stack != [] and stack[-1] != "(":
                answer.append(stack.pop())
        else:
            while stack != [] and operators[i] <= operators[stack[-1]]:
                answer.append(stack.pop())
            stack.append(i)
    while stack != []:
        answer.append(stack.pop())
    return "".join(answer).replace("(", "")

Notice in particular:

  • more space around the operators and between functions - less of a blob of characters.
  • no compressed one-liner if statements: only one "thought" should be on each line.

You may not consider this "efficient (in terms of size of code...)" as it's now spread over more lines, however I would argue size of code isn't the aim, the aim is actually:

  • simplicity and not-over engineered with unnecessary helper functions and abstract OOP.
  • portable and easy to share in a single file / copy-paste.
  • Quick and easy to read the entire thing.

... and re-formatting doesn't change any of those significantly, if at all. Performance is unrelated to formatting and I'm sure others will cover that aspect.

*Not really answer-worthy but too long for a comment

\$\endgroup\$
3
  • \$\begingroup\$ I'm surprised the PEP8 style doesn't recommend against PascalCasing the variables. \$\endgroup\$
    – IEatBagels
    Jan 10 at 14:58
  • 1
    \$\begingroup\$ @IEatBagels I said black was PEP8 compliant, but it is not a comprehensive implementation of the PEP8 guidelines, and will not for example re-case variables. I suppose this is because black only changes the appearance of code but not its meaning (enforced by comparing the AST/bytecode pre and post-formatting). Changing variable casing would modify your code's public API. I've updated my answer to clarify. You intuition is correct as PEP8 does in fact suggest snake_case for variables, functions and modules, PascalCase for classes and type aliases, YELLCASE_WITH_UNDERSCORES for constants. \$\endgroup\$
    – Greedo
    Jan 10 at 15:47
  • \$\begingroup\$ By Size of code I was trying to referencing to better implementation such as list compression instead using For loop adding to empty list which has an impact on , however this is due to me not explain exactly I was trying to achieve small implementiation. I did not think of formatting or even know about PEP8 but I can see it is much beneficial from the past experience.Thanks for the answer it was really helpful \$\endgroup\$ Jan 10 at 17:48
0
\$\begingroup\$

First some problems. (1) Your tokenizing function tries to accomplish the task character by character, but that fails if any operators are multi-character. (2) The tokenizer fails if the input string contains spaces, which seems user-unfriendly. (3) Because it returns the hard-earned results as an non-delimited string, the infix-to-postfix conversion function destroys the knowledge gleaned during the tokenizing phase.

# Problem 1: parser mangles the ** operator.
input: 12**6
output: 12*6*

# Problem 2: parser cannot tolerate spaces.
input: 12**6
output: KeyError

# Problem 3: converter destroys information.
input: 12+11-6
output: 1211+6-   # 12 and 11 became 1211. Seems bad.

A more powerful tokenizing strategy that is still simple. One of the easiest ways to build a simple tokenizer is to define a regular expression for each token and then to consume the input string one token at a time. As long as we use basic care in ordering the tokens (for example, we must hunt for ** before *), this strategy is easy to implement and to enhance if requirements evolve. It also has the advantage of performing token-level validation, meaning that it will raise an error if the input string fails to consist entirely of valid tokens. Here's the idea:

import re

# Note that ** must occur before * in the dict.
OPERATORS = {
    '(': 4,
    ')': 4,
    '^': 3,
    '**': 3,
    '*': 2,
    '/': 2,
    '+': 1,
    '-': 1,
}

# Our parser is just a regex defined as a bunch of alternatives:
# first the operators, then numbers/variables, and then whitespace.
PARSER = re.compile('|'.join(
    [re.escape(o) for o in OPERATORS] +
    [r'\w+', r'\s+']
))

def tokenize(infix):
    # Tokenize until the string is exhausted.
    # The i index tracks our current parsing location.
    i = 0
    STOP = len(infix)
    while i < STOP:
        m = PARSER.match(infix, pos = i)
        if m:
            tok = m.group(0)
            i += len(tok)
            # Yield only non-whitespace tokens.
            if tok.strip():
                yield tok
        else:
            raise ValueError(f'Invalid expression at position {i}: {infix!r}')

Your converter should be able to report unmatched parentheses. The shunting-yard algorithm is able to report parentheses problems, but you don't do that. In addition, other reviewers have noted a few other simplifications that can be made (eg, when checking for empty an stack) and have emphasized why cramped code is a bad idea. Here's an edited version of your code, with some comments mixed in to emphasize the key points:

def infix_to_postfix(infix):
    postfix = []
    stack = []
    LEFT = '('
    RIGHT = ')'
    for tok in tokenize(infix):
        # A simpler check for non-operator tokens.
        if tok not in OPERATORS:
            postfix.append(tok)
        # Named constants can enhance readability.
        elif tok == LEFT:
            stack.append(tok)
        elif tok == RIGHT:
            # Simpler checks for empty stack.
            while stack and stack[-1] != LEFT:
                postfix.append(stack.pop())
            # You can ditch the left parentheses here, and report errors.
            if stack and stack[-1] == LEFT:
                stack.pop()
            else:
                raise ValueError('Unmatched RIGHT')
        else:
            while stack and stack[-1] != LEFT and OPERATORS[tok] <= OPERATORS[stack[-1]]:
                postfix.append(stack.pop()) 
            stack.append(tok)
    # An easier way to push the rest of the stack.
    postfix.extend(reversed(stack))
    # Final check for unmatched parentheses.
    if LEFT in postfix:
        raise ValueError('Unmatched LEFT')
    # Return a list or tuple, not a string.
    return postfix
\$\endgroup\$
2
  • \$\begingroup\$ Thanks for mentioning problems against 1st function I will fix them. The provided infix_to_postfix function seems to be wrong as If you provided an expression with brackets such as (A+B)*C it raises Value error unmatched RIGHT since the stack is empty at if stack and stack[-1] == LEFT. Also, you are using f-strings with ValueError on the if blocks in infix_to_postfix is there a particular reason for it? \$\endgroup\$ Jan 11 at 7:30
  • \$\begingroup\$ @WhoEvenCaresToSeeTheName Fixed: needed an additional check when dealing with operators (stop when hitting LEFT). If I were starting from scratch, I would not model parentheses as operators. They are different, and are treated differently than operators, for example, in the Wikipedia pseudocode. \$\endgroup\$
    – FMc
    Jan 11 at 18:30

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.