Simple Infix to Postfix in Python

Today I wrote a Python program to transform an expression to reverse polish notation in order to solve the problem Transform the Expression and it worked fine. Here is my code:
def rpn(s):
    var_list = []
    symb_list = []
    for c in s:
        if c >= 'a' and c <= 'z':
            var_list.append(c)
        elif c in ['^', '*', '/', '+', '-']:
            symb_list.append(c)
        elif c == ')':
            x = var_list.pop()
            y = var_list.pop()
            z = symb_list.pop()
            var_list.append(y + x + z)
        #print var_list, symb_list
        
    return var_list[0]
        
t = int(raw_input())

while t:
    t -= 1
    s = raw_input()        
    print rpn(s)
The algorithm is very simple which you should be able to follow if you study my code. You can uncomment the line #print var_list, symb_list to see a simulation. Note that the Python program I wrote is not the perfect infix to postfix converter but it worked for the problem. The ideal program should work without taking the advantage of brackets. :-)

Comments

Unknown said…
Instead of using " if c >= 'a' and c <= 'z':" , use of " c.isaplpha() " will be more efficient, isn't it?
January 8, 2017 at 4:58 AM
Tamim Shahriar said…
There is no noticeable performance difference but c.isalpha() looks better.

>>> timeit.timeit('"c".isalpha()', number=100000)
0.010938495863229036
>>> timeit.timeit('"c" >= "a" and "c" <= "z"', number=100000)
0.00959616294130683
>>> timeit.timeit('"c" >= "a" and "c" <= "z"', number=100000)
0.011491957120597363
>>> timeit.timeit('"c".isalpha()', number=100000)
0.01122324913740158
>>>
January 8, 2017 at 9:04 AM
Post a Comment

Popular posts from this blog

Accept-Encoding 'gzip' to make your cralwer faster

Image
If you are looking for a way to make your web crawler / spider work faster, then you must be looking for reducing the time to fetch data from the Internet. Fortunately many websites provide the content in compressed format if the server gets such type of request. If you see the request header of Firefox (you can use firebug to see the request / response headers), you can find that it always asks for gzip content. If the server provides gzip, then it sends data in gzip form otherwise it sends html. gzip data reduces bandwidth and thus make the program to scrape / harvest data faster. So you can do the same from you Python code. Just add ('Accept-Encoding', 'gzip,deflate') in the request header. Check the following code chunk: opener = urllib2.build_opener() opener.addheaders = [('Referer', referer), ('User-Agent', uagent), ('Accept-Encoding', 'gzip,deflate')] usock = opener.open(url) url = usock.geturl() data = decode(usock) usock.c...
Read more

Python all any built-in function

I have been using Python for a long time, still learning lot of simple and new things. Recently I came to know about two built-in functions named all and any . Today while I was solving a hackerrank problem , I used both functions which makes the code a bit nicer, in my opinion. The functions compares two singly linked lists and if they are equal, returns 1, otherwise returns 0. Here is my code - def compare_lists(llist1, llist2): while all([llist1, llist2]): if llist1.data != llist2.data: return 0 llist1 = llist1.next llist2 = llist2.next if any([llist1, llist2]): return 0 return 1 Sometimes, this kind of simple thing brings joy to me. Let me know your thoughts. :)
Read more

lambda magic to find prime numbers

Find prime number up to 100 with just 3 lines of code. The 4th line is for printing ;) nums = range(2, 100) for i in range(2, 10):     nums = filter(lambda x: x == i or x % i, nums) print nums Isn't it amazing? Check my new post about Prime number: http://love-python.blogspot.com/2010/11/prime-number-generator-in-python-using.html
Read more