この記事では、java に関する関連知識を提供します。主に、算術式や論理式の一般的な表現方法として中置式を紹介します。中置式はコンピューターによって簡単に解析されませんが、人間の一般的な使用法に準拠しているため、依然として多くのプログラミング言語で使用されています。一緒に見てみましょう。皆さんのお役に立てれば幸いです。
推奨学習: 「java ビデオ チュートリアル 」
中置式とは 、後置式とは何ですか?
小学校の頃から習う四則演算、例えば 3 (5*(2 3) 7) このような式が中置式です。中置式は人間の脳にとって理解しやすく、各演算子の優先順位も人間の脳にとって判断しやすいので、最初に括弧内を計算し、次に*、次に-
を実行しますが、この式は非常にコンピュータの計算には適していません。コンピュータの計算を容易にするために、何らかの方法で接頭辞の式が接尾辞の式に変換されます。たとえば、3 (5*(2 3) 7) の接尾辞の式は 3,5,2 となります。 、3、、*、7、、。この式はコンピュータにとって計算しやすいのですが、なぜ計算しやすいのか、アルゴリズムフロー2で理解が深まります。
中置式を後置式に変換するには? たとえば、3 (5*(2 3) 7) を後置式に変換するプロセスはどのようなものですか? ?
演算子の優先順位:
と等しい
左括弧と右括弧は、特別な演算子として特別に扱われます。 (「(」に遭遇した場合は、優先度を判断する必要はなく、演算子スタックに直接進みます。「)」に遭遇した場合、優先度を判断する必要はなく、演算子から直接抜け出します。 stack)
大まかなアルゴリズムは次のプロセスを習得します。
2 つのスタックを用意します。1 つは数値スタック A、もう 1 つは演算子スタック (,-,*,/(,)) です。 B など。
1.0 数値スタック A については、数値が見つかった場合は、スタック A に直接入力します。
2.0 演算子スタック B には、いくつかの状況があります。
2.1 '(' 演算子が見つかった場合、スタックに直接プッシュされます。
2.2 ') が見つかった場合、演算子はスタックに直接プッシュされます。 ' 演算子、いいえ ')' が見つかるまで演算子スタック B のポップを停止します。 ('(' から ')' の間にポップされた演算子を順番にスタック A にプッシュします)
2.3 ',-,* /' に遭遇したとき、現在の要素 (現在の要素が現在のものであると仮定して) を比較します。 B stack 最上位演算子の優先順位 (スタックの最上位要素が最上位であると仮定)。
2.3.1 top >= current の場合、スタック B がポップされ、top
2.3.2 トップ
3.0 文字列内に演算子がある場合は、文字列全体をスキャンします。 B スタック、電流を 1 つずつスタックにポップします A
上記のアルゴリズムに従って 3 (5*(2 3) 7) のプロセスを示します:14, 文字列全体をスキャンし、B が空かどうかを確認します。空でない場合は、B スタックを置きます。要素が飛び出して A に入ります。現在空ではないので、最後のA スタックの要素は A: [3,5,2,3, ,*,7, , ]13、) に遭遇すると、スタック B をポップアップし、'(' に直接移動し、スタック A にポップアップ操作文字を実行します。 B:[ ] A:[3,5, 2,3, ,*,7, ]
1、遭遇3、そして 3 が A スタックに置かれます [3,]
2 、遭遇、B スタックに入る [ ,]
3、遭遇 (、B スタックに入る [ ,(]
4、遭遇 5, A スタック [3,5]
5 を入力、* に遭遇、* の優先順位は ( より大きい、B スタック [ ,(,*]
6 に遭遇、(、B スタック [ ,(,*) を入力,(]
7, エンカウント 2, A スタックに入る [3,5,2]
8, エンカウントしたら B スタックに入る [,(,*,(,, ]
9, エンカウント 3 ) に遭遇した場合、A スタック [3,5,2,3]
10 に入り、B スタックをポップし、'(' に直接移動し、ポップされた演算子を A スタックに置きます。B:[,( ,*] A:[3,5,2,3, ]
11 (エンカウントの優先順位) は B の先頭要素 * より小さいため、 * B からスタックをポップし、それを A に置き、そしてB:[ ,(, ] A:[3,5,2,3, ,* ]
12、7 が見つかったら、それをスタック A [3,5,2,3, , *,7]
したがって、A の最後の接尾辞は 3,5,2,3, となります。 ,*,7, ,
1、数値に遭遇したとき3、5、2、3、スタックに直接プッシュ A[3 ,5,2,3]を押します。上記のことからわかるように、コンピュータにとって計算は簡単で、結果は次のとおりです。左から右にスキャンして取得します。 3 コードの実装mid2post サフィックス式の検索calcPostExp サフィックス式の評価の取得cmpPriority 優先度の比較2、エンカウント、スタックの上部 2 と 3 をポップアップし、合計 5 になります。A[ をプッシュ3,5,5]
3, * に遭遇, スタックの上位 5 をポップアップ, 5. 乗算して 25 を得る. A[3,25]
4 をスタックにプッシュする. 7 に遭遇すると,スタック A[3,25,7]
5 に直接プッシュします。25 と 7 が見つかったら、スタックの一番上にポップアップします。32 を追加し、A[3,32]
6 をプッシュし、ヒットします。スタックの一番上に 3,32 をポップアップし、35 まで足し、A[35]
//优先级
bool cmpPriority(char top, char cur)//比较当前字符与栈顶字符的优先级，若栈顶高，返回true
{
if ((top == '+' || top == '-') && (cur == '+' || cur == '-'))
return true;
if ((top == '*' || top == '/') && (cur == '+' || cur == '-' || top == '*' || top == '/'))
return true;
if (cur == ')')
return true;
return false;
}vector<string> mid2post(string &str)
{
vector<string>vstr;
stack<char>cstack;
for (int i = 0;i<str.size();++i)//扫描字符串
{
string temp = "";
if (str[i] >= '0' && str[i] <= '9')//若是数字
{
temp += str[i];
while (i + 1<str.size() && str[i + 1] >= '0' && str[i + 1] <= '9')
{
temp += str[i + 1];//若是连续数字
++i;
}
vstr.push_back(temp);
}
else if (cstack.empty() || str[i] == '(')//若栈空或者字符为'('
cstack.push(str[i]);
else if (cmpPriority(cstack.top(), str[i]))//若栈顶元素优先级较高，栈顶元素出栈
{
if (str[i] == ')')//若当前字符是右括号，栈中元素出栈，入字符串数组中，直到遇到'('
{
while (!cstack.empty() && cstack.top() != '(')
{
temp += cstack.top();
cstack.pop();
vstr.push_back(temp);
temp = "";
}
cstack.pop();
}
else//栈中优先级高的元素出栈，入字符串数组，直到优先级低于当前字符
{
while (!cstack.empty() && cmpPriority(cstack.top(), str[i]))
{
temp += cstack.top();
cstack.pop();
vstr.push_back(temp);
temp = "";
}
cstack.push(str[i]);
}
}
else//当前字符优先级高于栈顶元素，直接入栈
cstack.push(str[i]);
}
while (!cstack.empty())//栈中还存在运算符时，出栈，存入字符串数组
{
string temp = "";
temp += cstack.top();
cstack.pop();
vstr.push_back(temp);
}
return vstr;
}int calcPostExp(vector<string> & vstr)//对后缀表达式进行求值，主要是根据运算符取出两个操作数进行运算
{
int num, op1, op2;
stack<int>opstack;
for (int i = 0;i<vstr.size();++i)
{
string temp = vstr[i];
if (temp[0] >= '0' && temp[0] <= '9')//如果当前字符串是数字，利用字符串流转化为int型
{
stringstream ss;
ss << temp;
ss >> num;
opstack.push(num);
}
else if (vstr[i] == "+")//若是操作符，取出两个操作数，进行运算，并将结果存入
{
op2 = opstack.top();
opstack.pop();
op1 = opstack.top();
opstack.pop();
opstack.push(op1 + op2);
}
else if (vstr[i] == "-")
{
op2 = opstack.top();
opstack.pop();
op1 = opstack.top();
opstack.pop();
opstack.push(op1 - op2);
}
else if (vstr[i] == "*")
{
op2 = opstack.top();
opstack.pop();
op1 = opstack.top();
opstack.pop();
opstack.push(op1*op2);
}
else if (vstr[i] == "/")
{
op2 = opstack.top();
opstack.pop();
op1 = opstack.top();
opstack.pop();
opstack.push(op1 / op2);
}
}
return opstack.top();//最终的栈顶元素就是求解的结果
}Java ビデオ チュートリアル "
以上がインスタンス解析 Java infix 式の実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
