Program to evaluate s-expression as string in Python

Suppose we have a string s as S-expression. We have to evaluate that S-expression and return result as integer. As we know that the s-expression is an expression which is either one number, or a recursive expression wrapped in parentheses like (+ (- 3 2) (* 3 3)), which indicates (3 - 2) + (3 * 3) = 10. Here valid operators are +, -, *, and /.

So, if the input is like s = "(- (+ 3 2) 2)", then the output will be 3, as ((3 + 2) - 2) = 3.

To solve this, we will follow these steps −

• stack := a new stack

• remove the opening and closing parenthesis of s

• a := split s using spaces and make a list of partitions

• for each i in a in reverse order, do

  • if size of i > 1, then

    • if i[0] is same as "-", then

      • push i as integer into stack

      • go for next iteration

    • otherwise,

      • push i as integer into stack

  • otherwise when i is a digit, then

    • push i as integer into stack

  • otherwise,

    • if size of stack >= 2, then

      • num1 := pop from stack

      • num2 := pop from stack

      • if i is same as "+", then

        • perform num1 + num2 and push into stack

      • otherwise when i is same as "-", then

        • perform num1 - num2 and push into stack

      • otherwise when i is same as "*", then

        • perform num1 * num2 and push into stack

      • otherwise,

        • perform num1 / num2 and push into stack

• return top element from stack, and remove top element

Example  

Let us see the following implementation to get a better understanding −

 Live Demo

class Solution:    def solve(self, s):       stack = list()       s = s.replace("(", "")       s = s.replace(")", "")       a = s.split()       for i in a[::-1]:          if len(i) > 1:             if i[0] == "-":                stack.append(int(i))                continue             else:                stack.append(int(i))          elif i.isdigit():             stack.append(int(i))          else:             if len(stack) >= 2:                num1 = stack.pop()                num2 = stack.pop()                if i == "+":                   stack.append(int(num1 + num2))                elif i == "-":                   stack.append(int(num1 - num2))                elif i == "*":                   stack.append(int(num1 * num2))                else:                   stack.append(int(num1 / num2))       return stack.pop() ob = Solution() s = "(- (+ 3 2) 2)" print(ob.solve(s))

Input

s = "(- (+ 3 2) 2)"

Output

3