Я работал над написанием программы Java для преобразования из инфиксной нотации в префиксную нотацию с использованием стека операндов и стека операторов. Я реализовал рабочий преобразователь на основе псевдокода в верхнем ответе здесь:
преобразование инфикса в префикс
Однако сейчас я пытаюсь определить временную и пространственную сложность вышеуказанного алгоритма.
Я думаю, что пространственная сложность должна быть 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
