Infix to Postfix | CodeChef

CodeChef-DSA-learners
#1

Hello,

My doubt is regarding associativity of the operators.

Can someone tell me if the usual right associativity apply for ‘^’ operator and left associativity for all other operators or should I assume similar associativity for each operator?

Thanks

#2

‘^’ (Exponent) has right to left associativity.

#3

Please note there there seems to be a problem with your test case files. Right associativity for ‘^’ is not followed.

I got AC for the submission: https://www.codechef.com/viewsolution/31674786 which converts A^B^C^D into AB^C^D^ which essentially means (((A^B)^C)^D) = A^(BCD) which should be deemed incorrect

I got WA for the submission: https://www.codechef.com/viewsolution/31656308
which converts A^B^C^D into ABCD^^^ which is the correct postfix conversion following right associativity of ‘^’

#4

Yes you are correct about that, the one that gave you wrong answer is the correct postfix form of A^B^C^D.

#5 
try:
test_cases = int(input())
for z in range(test_cases):

    n = int(input())
    memory = list(input())
    print(z)
    stack = ["("]
    postfix = []
    prefence = {"*": 2, "/": 2, "+": 1, "-": 1, "^": 3}
    brakets = ["(", ")"]


    def infixpsotfix(element):
        for element in memory:

            if element not in brakets and element not in prefence:
                postfix.append(element)
            elif element in prefence or element in brakets:

                if element in prefence:
                    if stack[-1] in prefence and prefence[stack[-1]] < prefence[element] and element in prefence:
                        stack.append(element)


                    elif stack[-1] in prefence and prefence[stack[-1]] >= prefence[element]:
                        poped = stack.pop()

                        stack.append(element)
                        postfix.append(poped)
                    else:
                        stack.append(element)
                if element in brakets and element == "(":
                    stack.append(element)
                elif element in brakets and stack[-1] == "(":
                    pass
                elif element in brakets and element == ")":
                    for i in range(len(stack)):
                        pope = stack.pop()
                        if pope != "(":

                            postfix.append(pope)
                        else:
                            break


    infixpsotfix(memory)
    for ii in range(len(stack)):

        if stack[len(stack)-ii-1] == "(":
            break
        else:
            postfix.append(stack[len(stack)-ii-1])

    print("".join(postfix))

except:
pass

this is my Code Please any one Tell me Why WA

#6

I think the associativity for ^(Bitwise exclusive OR) is from left to right… everyone is assuming ^ as exponent operator… which is not correct…