0

オペランド スタックと演算子スタックを使用して中置記法から前置記法に変換する Java プログラムの作成に取り組んでいます。ここの一番上の回答の疑似コードに基づいて、機能するコンバーターを実装しました。

接頭辞から接頭辞への変換

ただし、現在、上記のアルゴリズムの時間と空間の複雑さを解決しようとしています。

スペースの複雑さは O(n) でなければならないと思います。なぜなら、それらの間で共有される入力を格納する 2 つのスタックしかないからです。

時間の複雑さについて考えると、完全にはわかりませんが、各サブパートをインフィックスからプレフィックスに変換する必要があるため、O(n^2) ですか? この部分についてはよくわかりません。

基本的に私の質問は次のとおりです:私の空間複雑度の結果は正しいですか?アルゴリズムの時間複雑度はどれくらいですか?

どうもありがとう！

編集: これはアルゴリズムの擬似コードです:

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
4

1 に答える 1

2

ええ、O(n^2) は正しいように見えます - 基本的に外側と内側の while ループがあるからです。

編集: O(m *n) ここで m <= n ですが、それでも二次関数です

于 2012-11-09T05:18:28.100 に答える