私は、以下の式の中置記法から研磨記法への変換を理解できなかった試験の準備をしています:
(a–b)/c*(d + e – f / g)
指定された式がどのようにプレフィックスに変換されるかを段階的に説明できる人はいますか?
107515 次
14 に答える
27
Algorithm ConvertInfixtoPrefix
Purpose: Convert an 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
于 2010-01-09T20:37:07.973 に答える
6
(a–b)/c*(d + e – f / g)
接頭辞表記 (逆ポーランド語では演算子が最後にあり、どちらを意味するかは不明ですが、原理はまったく同じです):
(/ f g)(+ d e)(- (+ d e) (/ f g))(- a b)(/ (- a b) c)(* (/ (- a b) c) (- (+ d e) (/ f g)))
于 2009-12-22T19:24:17.547 に答える
5
中置詞と接頭辞の意味がよくわからない場合は、教科書のそのセクションを読み直すことを強くお勧めします。この 1 つの問題に対する正しい答えが得られたとしても、その概念を理解していないのであれば、あなたは何の得にもなりません。
アルゴリズム的には、非常に単純です。あなたはちょっとコンピューターのように振る舞うだけです。計算される順序ですべての計算を括弧で囲むことから始めます。次に、(最初の計算から最後の計算の順に) 左側の式の前に演算子を移動します。その後、括弧を削除して単純化できます。
于 2009-12-22T15:05:36.820 に答える
4
(a–b)/c*(d + e – f / g)
ステップ1：(a-b)/c*(d+e- /fg))
ステップ2：(a-b)/c*(+de - /fg)
ステップ 3:(a-b)/c * -+de/fg
ステップ 4:-ab/c * -+de/fg
ステップ 5:/-abc * -+de/fg
ステップ 6:*/-abc-+de/fg
これはプレフィックス表記です。
于 2012-03-04T14:44:02.927 に答える
1
(a–b)/c*(d + e – f / g)
式を左端から右端にスキャンすることを覚えておいてください。括弧で囲まれた用語の開始は、WHICH COMES FIRST ルールに従います... *、/、% は同じレベルにあり、+ および - よりも高くなっています.... (ab) = -bc 接頭辞(ab) = bc- 後置の別の括弧内の用語: (d + e - f / g) = 最初に / を移動し、プラス '+' が最初にマイナスため息 '-' の前に来ます (これらは同じレベルにあることに注意してください.. ) (d + e - f / g) 移動 / 最初 (d + e - (/fg)) = プレフィックス (d + e - (fg/)) = 後置 + その後 - ((+de) - (/ fg)) = プレフィックス ((de+) - (fg/)) = ポストフィックス
(-(+de)(/fg)) = 接頭辞なので、新しい式は -+de/fg (1) ((de+)(fg/)-) = 接尾辞なので、新しい式は de+fg/- になります(2)
(a–b)/c* したがって
(ab)/c*(d + e – f / g) = -bc 接頭辞 [-ab]/c*[-+de/fg] ---> (1) から引用 / c * まだ動かないので/[-ab]c * [-+de/fg] 次に、'*' を一番右に移動します。
- / [-ab]c[-+de/fg] = グループ記号を削除 = */-abc-+de/fg --> プレフィックス
(ab)/c*(d + e – f / g) = bc- for postfix [ab-]/c*[de+fg/-]---> (2) から取得したため、'/' が前に来る' ' は同じレベルにあるため、'/' を一番左に移動: [ab-]c [de+fg/-]/ 次に ' ' を一番左に移動 [ab-] c [de+fg/-]/ = グループ化記号を削除します= ab - cde + fg / - / * --> Postfix
于 2011-02-07T09:48:39.253 に答える
0
簡単なグーグル検索がこれを思いついた. 誰でもこれを簡単に説明できるとは思えません。しかし、編集後、あなたが自分の質問に答えることができるように、概念を前進させることができると思います.
ヒント:
試験勉強、がんばってね。あなたを予測して、成績が高くなります、私はそうします:D
説明 ：
操作をオペランドに関連付ける方法がすべてです。各表記タイプには独自の規則があります。これらのルールを分解して覚えておくだけです。(2*2)/3 を [* /] (2,2,3) と書いたと言ったら、後者の表記法を前者の表記法に変換する方法を学ぶだけです。
私のカスタム表記では、最初の 2 つのオペランドを取り、それらを乗算してから、結果のオペランドを 3 番目で割る必要があります。それを得る ？彼らはあなたに3つのことを教えようとしています。
- 異なる表記法に慣れるため。私が挙げた例は、アセンブリ言語で見られるものです。オペランド (操作対象) と演算 (オペランドに対して実行する内容)。
- コンピューティングにおける優先順位規則は、必ずしも数学で見られるものに従う必要はありません。
- 評価: マシンがプログラムを認識する方法と、実行時にプログラムを順序付ける方法。
于 2009-12-22T15:01:42.147 に答える
0
https://en.wikipedia.org/wiki/Shunting-yard_algorithm
分流ヤード アルゴリズムを適用して、接頭表記 (ポーランド表記とも呼ばれます) を生成することもできます。これを行うには、解析するトークンの文字列の末尾から開始して逆方向に作業し、出力キューを逆にして (したがって、出力キューを出力スタックにします)、左右の括弧の動作を反転します (今は-左括弧の動作は、右括弧が見つかるまでポップする必要があります)。
from collections import deque
def convertToPN(expression):
precedence = {}
precedence["*"] = precedence["/"] = 3
precedence["+"] = precedence["-"] = 2
precedence[")"] = 1
stack = []
result = deque([])
for token in expression[::-1]:
if token == ')':
stack.append(token)
elif token == '(':
while stack:
t = stack.pop()
if t == ")": break
result.appendleft(t)
elif token not in precedence:
result.appendleft(token)
else:
# XXX: associativity should be considered here
# https://en.wikipedia.org/wiki/Operator_associativity
while stack and precedence[stack[-1]] > precedence[token]:
result.appendleft(stack.pop())
stack.append(token)
while stack:
result.appendleft(stack.pop())
return list(result)
expression = "(a - b) / c * (d + e - f / g)".replace(" ", "")
convertToPN(expression)
ステップスルー:
step 1 : token ) ; stack:[ ) ]
result:[ ]
step 2 : token g ; stack:[ ) ]
result:[ g ]
step 3 : token / ; stack:[ ) / ]
result:[ g ]
step 4 : token f ; stack:[ ) / ]
result:[ f g ]
step 5 : token - ; stack:[ ) - ]
result:[ / f g ]
step 6 : token e ; stack:[ ) - ]
result:[ e / f g ]
step 7 : token + ; stack:[ ) - + ]
result:[ e / f g ]
step 8 : token d ; stack:[ ) - + ]
result:[ d e / f g ]
step 9 : token ( ; stack:[ ]
result:[ - + d e / f g ]
step 10 : token * ; stack:[ * ]
result:[ - + d e / f g ]
step 11 : token c ; stack:[ * ]
result:[ c - + d e / f g ]
step 12 : token / ; stack:[ * / ]
result:[ c - + d e / f g ]
step 13 : token ) ; stack:[ * / ) ]
result:[ c - + d e / f g ]
step 14 : token b ; stack:[ * / ) ]
result:[ b c - + d e / f g ]
step 15 : token - ; stack:[ * / ) - ]
result:[ b c - + d e / f g ]
step 16 : token a ; stack:[ * / ) - ]
result:[ a b c - + d e / f g ]
step 17 : token ( ; stack:[ * / ]
result:[ - a b c - + d e / f g ]
# the final while
step 18 : token ( ; stack:[ ]
result:[ * / - a b c - + d e / f g ]
于 2015-11-27T03:30:07.820 に答える
0
このアルゴリズムは、理解を深めるのに役立ちます。
ステップ 1. STACK に「)」を押し、A の末尾に「(」を追加します。
ステップ 2. A を右から左にスキャンし、STACK が空になるまで、A の各要素に対してステップ 3 から 6 を繰り返します。
ステップ 3. オペランドが検出された場合は、それを B に追加します。
ステップ 4. 右括弧が検出された場合は、それを STACK にプッシュします。
ステップ 5. オペレーターに遭遇した場合: STACK から繰り返しポップし、演算子と同じかそれ以上の優先順位を持つ (STACK の上部にある) 各演算子を B に追加します。b. STACK にオペレーターを追加します。
ステップ 6. 左括弧が encontered の場合 a. STACK からポップして B に追加することを繰り返します (左括弧に遭遇するまでスタックの一番上にある各演算子) b. 左括弧を削除します。
ステップ 7.終了
于 2015-06-15T14:39:26.580 に答える
-1
多分あなたは逆ポーランド記法について話しているのですか？はいの場合は、ウィキペディアで変換の非常に詳細なステップごとの例を見つけることができます。そうでなければ、あなたが何を求めているのかわかりません:(
また、そのような実装を提供した別の質問に対する私の回答を読みたいと思うかもしれません: C++ 単純操作 (+,-,/,*) 評価クラス
于 2009-12-22T15:01:39.400 に答える
-2
スタックを利用したアルゴリズムです。
これらの簡単な手順に従ってください。
1.指定された中置式を逆にします。
2. '(' を ')' に、')' を '(' に
置き換え
ます
。
ステップ 3 が難しいと判断した場合は、 http://scanftree.com/Data_Structure/infix-to-prefixを参照してください
。ここでは、実際の例も示されています。
于 2014-07-20T14:12:35.877 に答える