接尾辞式を接尾辞に変換
1.アルゴリズムの説明
例えばa+b*cこれは一般的な接尾辞式ですが、計算を容易にするために、コンピュータでは接尾辞式abc*+の形式に変換することがよくあります.
どのように変換しますか?
使用するキーデータ構造:スタック
変換の主な原則:
1.優先度の判断:演算子の優先度を比較することが重要です.優先度が高い人は、前の式に表示されます.カッコが付いているときはカッコの優先度が最も高く、*
例:その次に+-最後に.上の式では+の優先度が*より高くないため、接尾辞式では*が+の前に現れ、
2.オペランド処理:オペランドに遭遇したときは常に直接出力し、比較しない
3.括弧処理:左括弧に遭遇した場合は常に直接スタックに入り、右括弧に遭遇した場合は常にスタックを弾き、左括弧に遭遇するまで弾き続ける
4.優先度処理:オペレータに遭遇した場合は、まずそのオペレータとその前のオペレータを優先度比較する
a.前(スタックトップ)より優先度が高く、先にスタックを押す.
b.前のオペレータの優先度を下回るか等しいかは、前の優先度がそれより高いか等しいかの順序を弾き出し、優先度がそれより低いかスタックの頂上に着くまで弾き出し、スタックを押さえる.
2.優先度
Enum{FLAG=-1,//FLAGはスタックトップフラグであり、優先度が最も低く、任意のオペレータがスタックを押すことができることを目的としている(4.優先度処理に説明がある)
L_BRCAKET=0,//次と上、目的はすべてのオペレータが(その後スタックを押す(3.かっこ処理)
PLUS=1、//それからその他は通常の規定に従います
MINUS = 1,
MULTIPLY = 2,
DIVISON = 2,
PERSENT = 2,
POWER = 2};
それぞれ左かっこ、加減乗除の優先度定義で、ここにはFLAG=-1がある.何してるの?
上の4点を分析すると、最初のオペレータがスタックに入る前に前のオペレータと優先度を比較するなど、いくつかの特例があります.
しかし、オペレータがまだ存在しない場合は、スタックが空であるかどうかを判断してから、フラグ記号をスタックに押し込むと、
他のすべてのオペレータの優先度を下回る優先度を設定すると、いつまでもポップアップされず、特例的な判断が排除されます.これはテクニックです.
また、左括弧の優先度を低い定義することも理にかなっている.私たちはいつも右かっこに出会ったときに左かっこを弾き出すからです.
3.判定疑似コード:
for(すべての文字を巡回){
if(デジタル)出力;
else{
if(左かっこ)入桟;
Else if(右かっこ)弾桟は、左かっこに遭遇するまで弾きます.
else{
オペレータの優先度を判断します.
if(スタックトップ優先度が現在の優先度より小さい){
圧屋
}else{
現在の優先度より小さいすべてのオペレータをスタックから出て、スタックに入ります.
}
}
}
}
4.コード
5.
注1:スタックstack.hと接尾辞式の計算はhttp://hao3100590.iteye.com/blog/1569122を参照
ありがとう!
例えばa+b*cこれは一般的な接尾辞式ですが、計算を容易にするために、コンピュータでは接尾辞式abc*+の形式に変換することがよくあります.
どのように変換しますか?
使用するキーデータ構造:スタック
変換の主な原則:
1.優先度の判断:演算子の優先度を比較することが重要です.優先度が高い人は、前の式に表示されます.カッコが付いているときはカッコの優先度が最も高く、*
例:その次に+-最後に.上の式では+の優先度が*より高くないため、接尾辞式では*が+の前に現れ、
2.オペランド処理:オペランドに遭遇したときは常に直接出力し、比較しない
3.括弧処理:左括弧に遭遇した場合は常に直接スタックに入り、右括弧に遭遇した場合は常にスタックを弾き、左括弧に遭遇するまで弾き続ける
4.優先度処理:オペレータに遭遇した場合は、まずそのオペレータとその前のオペレータを優先度比較する
a.前(スタックトップ)より優先度が高く、先にスタックを押す.
b.前のオペレータの優先度を下回るか等しいかは、前の優先度がそれより高いか等しいかの順序を弾き出し、優先度がそれより低いかスタックの頂上に着くまで弾き出し、スタックを押さえる.
2.優先度
Enum{FLAG=-1,//FLAGはスタックトップフラグであり、優先度が最も低く、任意のオペレータがスタックを押すことができることを目的としている(4.優先度処理に説明がある)
L_BRCAKET=0,//次と上、目的はすべてのオペレータが(その後スタックを押す(3.かっこ処理)
PLUS=1、//それからその他は通常の規定に従います
MINUS = 1,
MULTIPLY = 2,
DIVISON = 2,
PERSENT = 2,
POWER = 2};
それぞれ左かっこ、加減乗除の優先度定義で、ここにはFLAG=-1がある.何してるの?
上の4点を分析すると、最初のオペレータがスタックに入る前に前のオペレータと優先度を比較するなど、いくつかの特例があります.
しかし、オペレータがまだ存在しない場合は、スタックが空であるかどうかを判断してから、フラグ記号をスタックに押し込むと、
他のすべてのオペレータの優先度を下回る優先度を設定すると、いつまでもポップアップされず、特例的な判断が排除されます.これはテクニックです.
また、左括弧の優先度を低い定義することも理にかなっている.私たちはいつも右かっこに出会ったときに左かっこを弾き出すからです.
3.判定疑似コード:
for(すべての文字を巡回){
if(デジタル)出力;
else{
if(左かっこ)入桟;
Else if(右かっこ)弾桟は、左かっこに遭遇するまで弾きます.
else{
オペレータの優先度を判断します.
if(スタックトップ優先度が現在の優先度より小さい){
圧屋
}else{
現在の優先度より小さいすべてのオペレータをスタックから出て、スタックに入ります.
}
}
}
}
4.コード
#include <iostream>
#include "stack.h"
#include <cstring>
using namespace std;
//
enum{ FLAG = -1, // FLAG , , ,
L_BRACKET = 0, //
PLUS = 1,
MINUS = 1,
MULTIPLY = 2,
DIVISON = 2,
PERSENT = 2,
POWER = 2;
};
//
int getPri(char ch){
switch(ch){
case '+':
return PLUS;
case '-':
return MINUS;
case '*':
return MULTIPLY;
case '/':
return DIVISON;
case '%':
return PERSENT;
case '^':
return POWER;
case '(':
return L_BRACKET;
case '#':
return FLAG;
}
}
//
bool isOper(char ch){
if((ch == '+') || (ch == '-') || (ch == '*') || (ch == '/') || (ch == '%') || (ch == '^'))
return true;
return false;
}
//
bool isBracket(char ch){
if(ch == '(' || ch == ')')
return true;
else
return false;
}
int main(){
//string infix = "10/(2+3)"; (1+2)/2+(3+5)*7; "2*3/5-(2*3)"
string infix = "(1+2+3)/2/3+(3+5)*7";
cout<<" :"<<infix<<endl;
stack<char> opt; //
opt.push('#'); //#
int len = infix.length();
int flag = 0; //
char* result = new char[len]; //
for (int i = 0; i < len; i++)
{
char ch = infix.at(i);
//1. , ,
if(!isOper(ch) && !isBracket(ch)){
result[flag++] = ch;
}
//2. , , ( ,
else{
if(ch == '('){ //a.(
opt.push(ch);
}else if(ch == ')'){ //b. ) , , (
while(opt.top() != '('){
result[flag++] = opt.pop();
}
opt.pop(); // '('
}else{ //c. +,-,*,/...
char t = opt.top(); // ,
int pre = getPri(t);
int cur = getPri(ch);
//A. 1: ,
//( , '#' -1, '(' 0, )
if(cur > pre){
opt.push(ch);
}
//B. 2: , , ,
else{
result[flag++] = opt.pop();
pre = getPri(opt.top());
while(pre >= cur){
result[flag++] = opt.pop();
pre = getPri(opt.top());
}
opt.push(ch); // ( ) ch
}
}
}
}
char ch = opt.top(); //
while (ch != '#')
{
result[flag++] = ch;
opt.pop();
ch = opt.top();
}
//
cout<<" :";
for(int i=0; i<flag; i++){
cout<<result[i];
}
cout<<endl;
delete[] result;
return 0;
}
5.
注1:スタックstack.hと接尾辞式の計算はhttp://hao3100590.iteye.com/blog/1569122を参照
ありがとう!