Leetcode: 1597. Build Binary Expression Tree From Infix Expression

# Definition for a binary tree node.
# class Node(object):
#     def __init__(self, val=" ", left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def expTree(self, s: str) -> "Node":
        s = "(" + s + ")"
        precedence = {"+": 1, "-": 1, "*": 2, "/": 2}
        posfix = []
        st = []
        for c in s:
            if c.isdigit():
                posfix.append(c)
            elif c == "(":
                st.append(c)
            elif c == ")":
                while st and st[-1] != "(":
                    posfix.append(st.pop())
                st.pop()
            else:
                while st and st[-1] != "(" and precedence[c] <= precedence[st[-1]]:
                    posfix.append(st.pop())
                st.append(c)
        ans = []
        for c in posfix:
            if c.isdigit():
                ans.append(Node(c))
            else:
                right = ans.pop()
                left = ans.pop()
                ans.append(Node(c, left, right))
        return ans[0]