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…

7

I am getting Runtime Error for my code.
But I am unable to figure out any error in my code and all my custom test cases are working completely fine.
Can anyone please help me find the error.
Link to my solution:
https://www.codechef.com/viewsolution/46523847