label each line for determining the Big-O of the infixToPostfix function. Find t
ID: 3792907 • Letter: L
Question
label each line for determining the Big-O of the infixToPostfix function. Find the Big-O and the values of c and n0.
sting 3 7.py CAUserslv ncenzoDesktop Algorithms HwListingsilisting 3 7.py File Edit Format Run Options Window Help from pythonds .basic import Stack import string def infixToPostfix (infix expr) prec prec prec prec prec prec 1 op Stack Stack postfix List toke List infix expr. split for token in toke if token in string ascii uppercase: post fix List.append (token) elif toke ena opStack. push (token) elif toke ena top Token op Stack. pop while topToken postfix List append (topToken) top Token op Stack. pop else: while (not opStack.isEmpty and (prec CopStack peek precltoke nj) postfix List append (opStack .pop opStack. push (token) while not opStack isEmpty postfix List.append (opStack.pop return. join (postfix ListExplanation / Answer
It is the problem of conversion of infix expression to postfix expression. The time complexity of this function is O(n) and n is the length of infix string. Every character in a string is accessed only once. No element is pushed, pop or print twice. Whether, there is three loop in the program, but it is not increasing the time complexity.
So the time complexity of this program is O(n) with n0>1 and c>1. For any infix string, it is not greater than n. It will also satisfy with n0 and c values.
Explanation
1. In the starting, we have set the priority to the each operator.
2. then we have tokenize the infix string.
3. now we are checking every token.
4. If the token is a character then we are simply printing it into postfix string.
5. if the token is '(' then we push to the stack. we continuously pop the operators till '(' if we get ')'.
6. if the list is not empty and stack operator has higher precedence than current operator, so we will pop the operator and add to postfix string till we get lower priority operator in stack or stack is empty. then we will push the current operator.
7. In the last, we pop all the operators and add it into the string of postfix expression.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.