Databases
StackOverflow2013
Postsdbo
POinfix to prefix time and space complexity
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POinfix to prefix time and space complexity
    primarykey
    data
    text
    <p>I have been working on writing a Java program to convert from infix notation to prefix notation using an operand stack and an operator stack. I have implemented a working converter based on the pseudocode in the top answer here:</p> <p><a href="https://stackoverflow.com/questions/1946896/conversion-from-infix-to-prefix">conversion from infix to prefix</a></p> <p>However I am now trying to work out the time and space complexity of the above algorithm. </p> <p>I think that the space complexity must be O(n) because we just have two stacks that store the input shared between them. </p> <p>Thinking about the time complexity, I'm not entirely sure, is it O(n^2) because of having to convert each subpart from infix to prefix? I'm not really sure about this part.</p> <p>Basically my question is: is my space complexity result correct, and what is the time complexity of the algorithm?</p> <p>Many thanks!</p> <p><strong>EDIT:</strong> This is the pseudocode for the algorithm:</p> <pre><code>Algorithm ConvertInfixtoPrefix Purpose: Convert and infix expression into a prefix expression. Begin // Create operand and operator stacks as empty stacks. Create OperandStack Create OperatorStack // While input expression still remains, read and process the next token. while( not an empty input expression ) read next token from the input expression // Test if token is an operand or operator if ( token is an operand ) // Push operand onto the operand stack. OperandStack.Push (token) endif // If it is a left parentheses or operator of higher precedence than the last, or the stack is empty, else if ( token is '(' or OperatorStack.IsEmpty() or OperatorHierarchy(token) &gt; OperatorHierarchy(OperatorStack.Top()) ) // push it to the operator stack OperatorStack.Push ( token ) endif else if( token is ')' ) // Continue to pop operator and operand stacks, building // prefix expressions until left parentheses is found. // Each prefix expression is push back onto the operand // stack as either a left or right operand for the next operator. while( OperatorStack.Top() not equal '(' ) OperatorStack.Pop(operator) OperandStack.Pop(RightOperand) OperandStack.Pop(LeftOperand) operand = operator + LeftOperand + RightOperand OperandStack.Push(operand) endwhile // Pop the left parthenses from the operator stack. OperatorStack.Pop(operator) endif else if( operator hierarchy of token is less than or equal to hierarchy of top of the operator stack ) // Continue to pop operator and operand stack, building prefix // expressions until the stack is empty or until an operator at // the top of the operator stack has a lower hierarchy than that // of the token. while( !OperatorStack.IsEmpty() and OperatorHierarchy(token) lessThen Or Equal to OperatorHierarchy(OperatorStack.Top()) ) OperatorStack.Pop(operator) OperandStack.Pop(RightOperand) OperandStack.Pop(LeftOperand) operand = operator + LeftOperand + RightOperand OperandStack.Push(operand) endwhile // Push the lower precedence operator onto the stack OperatorStack.Push(token) endif endwhile // If the stack is not empty, continue to pop operator and operand stacks building // prefix expressions until the operator stack is empty. while( !OperatorStack.IsEmpty() ) OperatorStack.Pop(operator) OperandStack.Pop(RightOperand) OperandStack.Pop(LeftOperand) operand = operator + LeftOperand + RightOperand OperandStack.Push(operand) endwhile // Save the prefix expression at the top of the operand stack followed by popping // the operand stack. print OperandStack.Top() OperandStack.Pop() End </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. UStree-hacker
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. COPost your code or pseudo code
      singulars
      1. POinfix to prefix time and space complexity
      1. USsmk
    2. COOK I have added my pseudo code. The actual code is a lot longer and not as easy to understand.
      singulars
      1. POinfix to prefix time and space complexity
      1. UStree-hacker
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload