接頭辞、接尾辞、接尾辞式およびその相互変換Java実装
6062 ワード
一、接頭辞式から接頭辞式への変換
接尾辞式をあげます:a+b*c-(d+e)
まず、演算子の優先度に基づいて、すべての演算単位にかっこを付けます:((a+(b*c)-(d+e))
演算記号を対応する括弧の前に移動し、すべての括弧を削除して接頭辞式に変換します.
-( +(a *(bc)) +(de)) -> -+a*bc+de
演算記号を対応する括弧の後ろに移動し、すべての括弧を削除して接尾辞式に変換します.
((a(bc)* )+ (de)+ )- -> abc*+de+-
二、接頭辞式と接尾辞式の計算
接頭辞式の計算:右から左へ式をスキャンし、数字に出会ったときに数字をスタックに入れ、演算子に出会ったときにスタックの一番上の2つの数をポップアップし、演算子で対応する演算(スタックの一番上の要素opの一番上の要素)を行い、結果をスタックに入れ、式の一番左端まで繰り返し、最後に算出した値が式の結果になります.
接尾辞式の計算:式を左から右にスキャンし、数字に遭遇した場合、数字をスタックに押し込み、演算子に遭遇した場合、スタックの一番上の2つの数をポップアップし、演算子で対応する計算(次の一番上の要素opスタックの一番上の要素)を行い、結果をスタックに入れます.式の一番右端まで上記の手順を繰り返し、最後に演算した値が式の結果になります.
注意:ここではすべて前の要素opの後ろの要素ですが、接頭辞式は計算時に後ろの要素が先にスタックに入るので、スタックトップの要素opの次トップの要素です.接尾辞式は、前の要素が先にスタックに入るので、セカンダリトップ要素opスタックトップ要素です.
三、接頭辞式を接頭辞式に変換する
次の手順に従います.
(1)2つのスタックを初期化する:演算子スタックS 1と中間結果を格納するスタックS 2;
(2)右から左へのスキャン接尾辞式;
(3)操作数に遭遇した場合、S 2に押し込む.
(4)演算子に遭遇した場合、S 1スタックトップ演算子との優先度を比較する.
(4-1)S 1が空である場合、またはスタックトップ演算子が右かっこ")"である場合、この演算子を直接スタックに入れる.
(4−2)そうでなければ、スタックトップ演算子よりも優先度が高いか等しい場合、演算子もS 1に押し込む.
(4−3)そうでなければ、S 1スタックトップの演算子をS 2にポップアップし、再び(4−1)S 1の新しいスタックトップ演算子と比較する.
(5)括弧に遭遇した場合:
(5-1)右括弧")"であれば、S 1に直接圧入する.
(5−2)左括弧"("であれば、S 1スタックの上部の演算子を順次ポップアップし、右括弧に遭遇するまでS 2を押し込み、このときこの一対の括弧を破棄する.
(6)式の一番左になるまで、ステップ(2)~(5)を繰り返す.
(7)S 1の残りの演算子を順次S 2にポップアップして押し込む.
(8)S 2の要素を順次ポップアップして出力し、結果は接頭辞式に対応する接頭辞式である.
たとえば、接頭辞式「1+((2+3)×4)-5」を接頭辞式に変換する手順は、次のとおりです.
スキャンされた要素
S 2(スタックボトム->スタックトップ)
S 1(スタックボトム->スタックトップ)
説明
5
5
空
数値、直接スタック
-
5
-
S 1が空で、演算子が直接スタックに入る
)
5
- )
右かっこ直接スタック
4
5 4
- )
ディジタルダイレクトスタック
×
5 4
- ) ×
S 1スタックの上部は右かっこで、直接スタックに入る
)
5 4
- ) × )
右かっこ直接スタック
3
5 4 3
- ) × )
数値
+
5 4 3
- ) × ) +
S 1スタックの上部は右かっこで、直接スタックに入る
2
5 4 3 2
- ) × ) +
数値
(
5 4 3 2 +
- ) ×
左かっこ、ポップアップオペレータが右かっこに遭遇するまで
(
5 4 3 2 + ×
-
同上
+
5 4 3 2 + ×
- +
優先度:-と同じ、スタック
1
5 4 3 2 + × 1
- +
数値
左端に達する
5 4 3 2 + × 1 + -
空
S 1の残りの演算子
結果は「-+1」× + 2 3 4 5”.
四、接尾辞式を接尾辞式に変換する
接頭辞式に変換するのと同様に、次の手順に従います.
(1)2つのスタックを初期化する:演算子スタックS 1と中間結果を格納するスタックS 2;
(2)左から右へのスキャン接尾辞式;
(3)操作数に遭遇した場合、S 2に押し込む.
(4)演算子に遭遇した場合、S 1スタックトップ演算子との優先度を比較する.
(4-1)S 1が空である場合、またはスタックトップ演算子が左かっこ"("である場合、この演算子を直接スタックに入れる.
(4−2)そうでなければ、スタックトップ演算子よりも優先度が高い場合、演算子もS 1に押し込む(プレフィックス式に変換する場合は優先度が高いか同じであることに注意し、ここでは同じ場合を含まない).
(4−3)そうでなければ、S 1スタックトップの演算子をS 2にポップアップし、再び(4−1)S 1の新しいスタックトップ演算子と比較する.
(5)括弧に遭遇した場合:
(5-1)左括弧"("であれば、S 1に直接圧入する.
(5−2)右括弧")"の場合、S 1スタックの上部の演算子が順次ポップアップされ、左括弧に遭遇するまでS 2が押し込まれ、このときこの一対の括弧が破棄される.
(6)式の右端まで、ステップ(2)~(5)を繰り返す.
(7)S 1の残りの演算子を順次S 2にポップアップして押し込む.
(8)S 2の要素を順次ポップアップして出力し、結果の逆順は接頭辞式に対応する接尾辞式(接頭辞式に変換するときは逆順ではない)である.
たとえば、接頭辞式「1+((2+3)×4)-5」を接尾辞式に変換する手順は、次のとおりです.
スキャンされた要素
S 2(スタックボトム->スタックトップ)
S 1(スタックボトム->スタックトップ)
説明
1
1
空
数値、直接スタック
+
1
+
S 1が空で、演算子が直接スタックに入る
(
1
+ (
左かっこ、直接スタック
(
1
+ ( (
同上
2
1 2
+ ( (
数値
+
1 2
+ ( ( +
S 1スタックの上部は左かっこ、演算子は直接スタックに入る
3
1 2 3
+ ( ( +
数値
)
1 2 3 +
+ (
右かっこ、ポップアップ演算子が左かっこに遭遇するまで
×
1 2 3 +
+ ( ×
S 1スタックの上部は左かっこ、演算子は直接スタックに入る
4
1 2 3 + 4
+ ( ×
数値
)
1 2 3 + 4 ×
+
右かっこ、ポップアップ演算子が左かっこに遭遇するまで
-
1 2 3 + 4 × +
-
-+と同じ優先度なので、+をポップアップし、再押し込み-
5
1 2 3 + 4 × + 5
-
数値
最右端に達する
1 2 3 + 4 × + 5 -
空
S 1の残りの演算子
結果は「1 2 3+4× + 5-」(逆シーケンス出力が必要であることに注意).
五、プログラミング実現
参考資料:
http://blog.csdn.net/antineutrino/article/details/6763722
http://blog.csdn.net/sgbfblog/article/details/8001651
接尾辞式をあげます:a+b*c-(d+e)
まず、演算子の優先度に基づいて、すべての演算単位にかっこを付けます:((a+(b*c)-(d+e))
演算記号を対応する括弧の前に移動し、すべての括弧を削除して接頭辞式に変換します.
-( +(a *(bc)) +(de)) -> -+a*bc+de
演算記号を対応する括弧の後ろに移動し、すべての括弧を削除して接尾辞式に変換します.
((a(bc)* )+ (de)+ )- -> abc*+de+-
二、接頭辞式と接尾辞式の計算
接頭辞式の計算:右から左へ式をスキャンし、数字に出会ったときに数字をスタックに入れ、演算子に出会ったときにスタックの一番上の2つの数をポップアップし、演算子で対応する演算(スタックの一番上の要素opの一番上の要素)を行い、結果をスタックに入れ、式の一番左端まで繰り返し、最後に算出した値が式の結果になります.
接尾辞式の計算:式を左から右にスキャンし、数字に遭遇した場合、数字をスタックに押し込み、演算子に遭遇した場合、スタックの一番上の2つの数をポップアップし、演算子で対応する計算(次の一番上の要素opスタックの一番上の要素)を行い、結果をスタックに入れます.式の一番右端まで上記の手順を繰り返し、最後に演算した値が式の結果になります.
注意:ここではすべて前の要素opの後ろの要素ですが、接頭辞式は計算時に後ろの要素が先にスタックに入るので、スタックトップの要素opの次トップの要素です.接尾辞式は、前の要素が先にスタックに入るので、セカンダリトップ要素opスタックトップ要素です.
三、接頭辞式を接頭辞式に変換する
次の手順に従います.
(1)2つのスタックを初期化する:演算子スタックS 1と中間結果を格納するスタックS 2;
(2)右から左へのスキャン接尾辞式;
(3)操作数に遭遇した場合、S 2に押し込む.
(4)演算子に遭遇した場合、S 1スタックトップ演算子との優先度を比較する.
(4-1)S 1が空である場合、またはスタックトップ演算子が右かっこ")"である場合、この演算子を直接スタックに入れる.
(4−2)そうでなければ、スタックトップ演算子よりも優先度が高いか等しい場合、演算子もS 1に押し込む.
(4−3)そうでなければ、S 1スタックトップの演算子をS 2にポップアップし、再び(4−1)S 1の新しいスタックトップ演算子と比較する.
(5)括弧に遭遇した場合:
(5-1)右括弧")"であれば、S 1に直接圧入する.
(5−2)左括弧"("であれば、S 1スタックの上部の演算子を順次ポップアップし、右括弧に遭遇するまでS 2を押し込み、このときこの一対の括弧を破棄する.
(6)式の一番左になるまで、ステップ(2)~(5)を繰り返す.
(7)S 1の残りの演算子を順次S 2にポップアップして押し込む.
(8)S 2の要素を順次ポップアップして出力し、結果は接頭辞式に対応する接頭辞式である.
たとえば、接頭辞式「1+((2+3)×4)-5」を接頭辞式に変換する手順は、次のとおりです.
スキャンされた要素
S 2(スタックボトム->スタックトップ)
S 1(スタックボトム->スタックトップ)
説明
5
5
空
数値、直接スタック
-
5
-
S 1が空で、演算子が直接スタックに入る
)
5
- )
右かっこ直接スタック
4
5 4
- )
ディジタルダイレクトスタック
×
5 4
- ) ×
S 1スタックの上部は右かっこで、直接スタックに入る
)
5 4
- ) × )
右かっこ直接スタック
3
5 4 3
- ) × )
数値
+
5 4 3
- ) × ) +
S 1スタックの上部は右かっこで、直接スタックに入る
2
5 4 3 2
- ) × ) +
数値
(
5 4 3 2 +
- ) ×
左かっこ、ポップアップオペレータが右かっこに遭遇するまで
(
5 4 3 2 + ×
-
同上
+
5 4 3 2 + ×
- +
優先度:-と同じ、スタック
1
5 4 3 2 + × 1
- +
数値
左端に達する
5 4 3 2 + × 1 + -
空
S 1の残りの演算子
結果は「-+1」× + 2 3 4 5”.
四、接尾辞式を接尾辞式に変換する
接頭辞式に変換するのと同様に、次の手順に従います.
(1)2つのスタックを初期化する:演算子スタックS 1と中間結果を格納するスタックS 2;
(2)左から右へのスキャン接尾辞式;
(3)操作数に遭遇した場合、S 2に押し込む.
(4)演算子に遭遇した場合、S 1スタックトップ演算子との優先度を比較する.
(4-1)S 1が空である場合、またはスタックトップ演算子が左かっこ"("である場合、この演算子を直接スタックに入れる.
(4−2)そうでなければ、スタックトップ演算子よりも優先度が高い場合、演算子もS 1に押し込む(プレフィックス式に変換する場合は優先度が高いか同じであることに注意し、ここでは同じ場合を含まない).
(4−3)そうでなければ、S 1スタックトップの演算子をS 2にポップアップし、再び(4−1)S 1の新しいスタックトップ演算子と比較する.
(5)括弧に遭遇した場合:
(5-1)左括弧"("であれば、S 1に直接圧入する.
(5−2)右括弧")"の場合、S 1スタックの上部の演算子が順次ポップアップされ、左括弧に遭遇するまでS 2が押し込まれ、このときこの一対の括弧が破棄される.
(6)式の右端まで、ステップ(2)~(5)を繰り返す.
(7)S 1の残りの演算子を順次S 2にポップアップして押し込む.
(8)S 2の要素を順次ポップアップして出力し、結果の逆順は接頭辞式に対応する接尾辞式(接頭辞式に変換するときは逆順ではない)である.
たとえば、接頭辞式「1+((2+3)×4)-5」を接尾辞式に変換する手順は、次のとおりです.
スキャンされた要素
S 2(スタックボトム->スタックトップ)
S 1(スタックボトム->スタックトップ)
説明
1
1
空
数値、直接スタック
+
1
+
S 1が空で、演算子が直接スタックに入る
(
1
+ (
左かっこ、直接スタック
(
1
+ ( (
同上
2
1 2
+ ( (
数値
+
1 2
+ ( ( +
S 1スタックの上部は左かっこ、演算子は直接スタックに入る
3
1 2 3
+ ( ( +
数値
)
1 2 3 +
+ (
右かっこ、ポップアップ演算子が左かっこに遭遇するまで
×
1 2 3 +
+ ( ×
S 1スタックの上部は左かっこ、演算子は直接スタックに入る
4
1 2 3 + 4
+ ( ×
数値
)
1 2 3 + 4 ×
+
右かっこ、ポップアップ演算子が左かっこに遭遇するまで
-
1 2 3 + 4 × +
-
-+と同じ優先度なので、+をポップアップし、再押し込み-
5
1 2 3 + 4 × + 5
-
数値
最右端に達する
1 2 3 + 4 × + 5 -
空
S 1の残りの演算子
結果は「1 2 3+4× + 5-」(逆シーケンス出力が必要であることに注意).
五、プログラミング実現
String midToPost(String midSeq){
Stack<Character> S1 = new Stack<Character>();
Stack<Character> S2 = new Stack<Character>();
int len = midSeq.length();
int index = 0;
while(index < len){
char c = midSeq.charAt(index);
switch(c){
case '(':
S1.push(c);
break;
case ')':
while(S1.peek() != '(')
S2.push(S1.pop());
S1.pop();
break;
case '+':
case '-':
while(!S1.empty() && S1.peek() != '(')
S2.push(S1.pop());
S1.push(c);
break;
case '*':
case '/':
while(!S1.empty() && S1.peek().toString().matches("[*/]"))
S2.push(S1.pop());
S1.push(c);
break;
default:
S2.push(c);
}
index++;
}
while(!S1.empty())
S2.push(S1.pop());
Iterator<Character> iter = S2.iterator();
StringBuffer postSeq = new StringBuffer();
while(iter.hasNext())
postSeq.append(iter.next());
return postSeq.toString();
}
String midToPre(String midSeq){
Stack<Character> S1 = new Stack<>(); //S1
Stack<Character> S2 = new Stack<Character>(); //S2
int len = midSeq.length();
int index = len - 1;
while(index >= 0){
char c = midSeq.charAt(index);
switch(c){
case ')':
S1.push(c);
break;
case '(':
while(S1.peek() != ')'){
S2.push(S1.pop());
}
S1.pop();
break;
case '*':
case '/':
S1.push(c);
break;
case '+':
case '-':
if(S1.empty() || S1.peek().toString().matches("[+-]"))
S1.push(c);
else{
while(!S1.empty() && S1.peek().toString().matches("[*/]")){
S2.push(S1.pop());
}
S1.push(c);
}
break;
default:
S2.push(c);
}
index--;
}
while(!S1.empty())
S2.push(S1.pop());
StringBuffer preSeq = new StringBuffer();
Iterator<Character> iter = S2.iterator();
while(iter.hasNext())
preSeq.append(iter.next());
preSeq = preSeq.reverse();
return preSeq.toString();
}参考資料:
http://blog.csdn.net/antineutrino/article/details/6763722
http://blog.csdn.net/sgbfblog/article/details/8001651