시간과 공간의 접두사 접두사 접미사

Question

필자는 피연산자 스택과 연산자 스택을 사용하여 중위 표기법에서 접두사 표기법으로 변환하기 위해 Java 프로그램을 작성하는 중임. 여기 상단 대답의 의사에 따라 작동하는 컨버터를 구현 한 :

conversion from infix to prefix

그러나 지금은 시간과 위의 알고리즘의 공간 복잡도를 해결하려고 노력하고있다.

공간 복잡성은 O (n)이어야한다고 생각합니다. 두 개 스택 사이에 공유 된 입력을 저장하기 때문입니다.

시간 복잡성에 대해 생각해 볼 때, 각 하위 부분을 중위 어에서 접두어로 변환해야하므로 O (n^2)인지 확실하지 않습니다. 나는이 부분에 대해서 정말로 확신하지 못한다.

기본적으로 내 질문은 : 내 공간 복잡성 결과가 정확하고 알고리즘의 시간 복잡도가 무엇입니까?

감사합니다.

EDIT : 이는 알고리즘의 의사 코드는 다음과

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) > 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 

Answer 1

긍정 O (N^2)이 올 바르면 - 본질적으로는 외부 루프 동안 내부가 있기 때문이다.

편집 : O (m의 * n을) 여기서 m < = N,하지만 여전히 quadractic