Transform an algebraic expression with brackets into RPN (Reverse Polish Notation) form

Question

from sys import stdin
t=int(stdin.readline())
while(t):
    s=stdin.readline()
    str = []
    top=-1
    for i in range(0, len(s)):
        c=s.index(i)
        if(c>='a' and c<='z'):
            print(c)
        elif(c=='('):
            pass
        elif(c==')'):
            print(str[top])
            top-=1
        else:
            top+=1
            str[top] = c
    t-=1

Input:

1
(a+b)

Error:

Traceback (most recent call last):
  File "C:\Users\Anurag\AppData\Roaming\NetBeans\8.0.1\nb_test_runner.py", line 216, in <module>
    module = __import__(module_name, globals(), locals(), module_name)
  File "__pyclasspath__/opn.py", line 8, in <module>
Finished in 0.0 seconds.
TypeError: expected a str
0 tests, 0 failures, 0 errors

After providing 1 and (a+b) as input above error get displayed.

Answer 1

The reported error is happening because s.index() doesn't do what you think it does. s.index(substr) returns the index of substr in s. See the docs for details. Try

c = s[i]

or even better, change the start of the for loop to

for c in s:

There are a few other problems with your code. Eg, str[top] will fail if str is an empty list.

The code below will run, but the zstr = [None]*20 line is a band-aid solution & you really need to use better logic here. Also, your current algorithm requires expressions to be parenthesized, which is a bit limiting.

from sys import stdin

t = int(stdin.readline())
while t:
    s = stdin.readline()
    zstr = [None]*20
    top = -1
    for c in s:
        if c.islower():
            print(c)
        elif c=='(':
            pass
        elif c==')':
            print(zstr[top])
            top -= 1
        else:
            top += 1
            zstr[top] = c
    t-=1

Test

echo -e "2\n(x-y)\n((a+b)*(c+d))" | python qtest.py

Output

x
y
-
a
b
+
c
d
+
*

---

Edit

An efficient way to get all the output on one line is to gather the output strings into a list, and then join them into one string. OTOH, just keeping them in a list may be useful.

Also, it's a good idea to keep your processing logic separate from input and output, where practical. Of course, for a calculator program, that may not be practical.

rpntest.py

#! /usr/bin/env python

''' Transform an algebraic expression with brackets into RPN (Reverse Polish Notation) form
From http://stackoverflow.com/questions/26191707/transform-an-algebraic-expression-with-brackets-into-rpn-reverse-polish-notatio
'''

import sys
import readline

def to_rpn(s):
    rpn = []
    zstr = [None] * 20
    top = -1
    for c in s:
        if c.islower():
            rpn.append(c)
            #print c
        elif c=='(':
            pass
        elif c==')':
            rpn.append(zstr[top])
            #print zstr[top]
            top -= 1
        else:
            top += 1
            zstr[top] = c
    return ' '.join(rpn)


def main():
    #for line in sys.stdin:
    while True:
        try:
            line = raw_input()
        except EOFError:
            break
        if line == '':
            continue
        rpn = to_rpn(line)
        print rpn


if __name__ == '__main__':
    main()

I've changed the input logic of the program a little. Now you don't need to specify how many expressions to transform. The program still reads one algebraic expression per line, but it ignores blank lines. By importing readline, it also gives you some line editing ability, so the arrow keys can be used. To exit the program you need to send an End Of File signal - on Linux that's Ctrl-D, I think on Windows it's Ctrl-Z. You can still pipe input into the program, eg echo -e "(x-y)\n((a+b)*(c+d))" | python rpntest.py.