表达式树、解析和执行操作

Question

我在一个编码挑战中遇到了这个问题。我不能按时解决这件事，但我仍然想知道怎么做。我不太熟悉表达树，我发现很难模拟这个问题。描述如下：

输入： expression_tree | sequence_of_operations

输入是带有表达式树的单行文本和由|字符分隔并以\n换行符结尾的一系列操作。输入中允许使用空格，但应忽略它。

表达式树是由一个字符变量and组成的序列，由括号(expression_tree)构成的子表达式树。例子：AB，A(B C D)，(AB)C((DE)F)

操作序列是带有字符R (反向)或S (简化)的字符串。

反向意思是反转表达式树中所有事物的顺序。在一行中应用两次反向取消。示例：(AB)C((DE)F) | R应该打印(F(ED))C(BA)

简化意味着删除表达式树中第一个元素及其每个子表达式树周围的括号。多次应用S应该与应用S一次具有相同的结果。示例：(AB)C((DE)F) | S应该打印ABC(DEF)

输出：读取表达式树并将操作顺序从左到右应用到表达式树，打印结果时不带字符。

我最想知道的是如何建模表达式树来处理括号，以及简化操作应该如何工作？

Answer 1

'''
Examples are as follows :
INPUT:
(AB)(C(DE))/SS
(((AB)C)D)E/SS
(((AB)C)D)E/SR
(AB)C((DE)F)/SRS
(AB(CD((EF)G)H))(IJ)/SRS
(AB(CD((EF)G)H))(IJ)/SSSRRRS
(A(B(C)D)E(FGH(IJ)))/SRRSSRSSRRRSSRS
(A(BC(D(E((Z)K(L)))F))GH(IJK))/S
-------------------------------
OUTPUT:
AB(C(DE))
ABCDE
EDCBA
FEDCBA
JI(H(GFE)DC)BA
JI(H(GFE)DC)BA
JIHFGE(D(C)B)A
A(BC(D(E(ZK(L)))F))GH(IJK)/S
'''



'''
operationReverse function returns a reversed expression tree 
Example :  AB(CD) -> (DC)BA
'''
def operationReverse(expression):
    '''============== Reversing the whole expressions ================'''
    expression = expression[::-1] 
    expression = list(expression)

    '''========= Replace Closing brace with Opening brace and vice versa ========='''
    for x in range(0, len(expression)):
        if(expression[x] != ')' and expression[x] != '('):
            continue
        elif(expression[x] == ")"):
            expression[x] = "("
        else:
            expression[x] = ")"

    expression = ''.join(expression)
    return expression


'''
operationSimplify function returns a simplified expression tree 
Example :  (AB)(C(DE)) -> AB(C(DE))
operationSimplify uses recursion
'''
def operationSimplify(expression):

    '''========= If no parenthesis found then return the expression as it is because it is already simplified ========='''
    '''========= This is also the base condition to stop recursion ============='''
    if(expression.find('(')==-1):
        return expression


    '''If 1st character is opening brace then find its correspoinding closing brace and remove them and call the function by passing the values between the opening and                 closing brace'''

    if(expression[0] == '('):
        x = 1
        #numOfOpeningBrackets = maintains the count of opening brackets for finding it's corresponding closing bracket
        numOfOpeningBrackets = 1
        while(x < len(expression)):
            if(expression[x] != ')' and expression[x] != '('):
                x = x + 1
                continue
            elif(expression[x] == "("):
                numOfOpeningBrackets = numOfOpeningBrackets + 1
                x = x + 1
            else:
                numOfOpeningBrackets = numOfOpeningBrackets - 1   
                if(numOfOpeningBrackets == 0):
                    posOfCloseBracket = x
                    break         
                x = x + 1 
        expression = operationSimplify(expression[1:posOfCloseBracket]) + expression[posOfCloseBracket+1:]

    '''========= If no parenthesis found then return the expression as it is because it is already simplified ========='''
    if(expression.find('(')==-1):
        return expression

    '''========= Find the opening brace and it's closing brace and new expression tree will be concatenation of start of string till opening brace including the brace and string       with in the opening brace and closing brace passed as an argument to the function itself and the remaining string ========='''
    x = 0
    #numOfOpeningBrackets = maintains the count of opening brackets for finding it's corresponding closing bracket
    recursion = False
    numOfOpeningBrackets = 0
    while (x < len(expression)):
        if(expression[x] != ')' and expression[x] != '('):
                x = x + 1
        elif(expression[x] == "("):
            if(numOfOpeningBrackets == 0 or recursion == True):
                numOfOpeningBrackets = 0
                recursion = False
                posOfStartBracket = x
                y = x
            numOfOpeningBrackets = numOfOpeningBrackets + 1
            x = x + 1
        else:
            numOfOpeningBrackets = numOfOpeningBrackets - 1 
            if(numOfOpeningBrackets == 0):
                posOfCloseBracket = x 
                x = y 
                expression=expression[0:posOfStartBracket+1]+operationSimplify(expression[posOfStartBracket+1:posOfCloseBracket])+expression[posOfCloseBracket:]
                recursion = True
            x = x + 1
    return expression


'''
solution fucntion prints the final result  
'''
def solution(inputString):
    '''========= Remove the spaces from the input ==============='''
    #inputString = inputString.replace("\n","")
    inputString = inputString.replace(" ","")
    inputString = inputString.replace("\t","")
    #inputString = inputString.replace("()","")

    '''=============== The substring before '/' is expression tree and substring after '/' is sequence of operations  ======================'''

    #posOfSlash = Position Of Slash Character
    posOfSlash = inputString.find('/')
    if(posOfSlash == -1):
        print (inputString)
        return
    #expressionTree = Expression Tree
    expressionTree = inputString[0:posOfSlash]
    #seqOfOp = sequence of operations to be performed
    seqOfOp = inputString[posOfSlash+1:]

    '''============ If sequence Of Operations is empty then print the expression tree as it is ============== '''
    if(len(seqOfOp)==0):
        print(expressionTree)
        return


    '''============= Removing all the pairs of RR from the sequence Of Operations =================='''   
    seqOfOp = seqOfOp.replace(r+r,'')

    '''============ All mulptiple S are replaced by one single S ================'''   
    while(seqOfOp.find(s+s) != -1):
        seqOfOp = seqOfOp.replace(s+s,s)

    '''============ If to perform operation R then call operationReverse() else if to perform operation S call operationSimplify() ================'''
    for x in range (0 , len(seqOfOp)):
        if(seqOfOp[x] == r):
            expressionTree = operationReverse(expressionTree)
        else :
            expressionTree = operationSimplify(expressionTree)
    print(expressionTree)
    return



'''======= Global variables r and s representing operations R and S'''
r = 'R'
s = 'S' 
while True:
    try:
        inputString = input()
        '''==================== Calling function solution  ======================'''
        solution(inputString)
    except EOFError:
        break