インスタンス解析 Java infix 式の実装

この記事では、java に関する関連知識を提供します。主に、算術式や論理式の一般的な表現方法として中置式を紹介します。中置式はコンピューターによって簡単に解析されませんが、人間の一般的な使用法に準拠しているため、依然として多くのプログラミング言語で使用されています。一緒に見てみましょう。皆さんのお役に立てれば幸いです。

推奨学習: 「java ビデオ チュートリアル 」

1. 概念

中置式とは 、後置式とは何ですか?

小学校の頃から習う四則演算、例えば 3 (5*(2 3) 7) このような式が中置式です。中置式は人間の脳にとって理解しやすく、各演算子の優先順位も人間の脳にとって判断しやすいので、最初に括弧内を計算し、次に*、次に-

を実行しますが、この式は非常にコンピュータの計算には適していません。コンピュータの計算を容易にするために、何らかの方法で接頭辞の式が接尾辞の式に変換されます。たとえば、3 (5*(2 3) 7) の接尾辞の式は 3,5,2 となります。 、3、、*、7、、。この式はコンピュータにとって計算しやすいのですが、なぜ計算しやすいのか、アルゴリズムフロー2で理解が深まります。

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) のプロセスを示します:

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]

13、) に遭遇すると、スタック B をポップアップし、'(' に直接移動し、スタック A にポップアップ操作文字を実行します。 B:[ ] A:[3,5, 2,3, ,*,7, ]

14, 文字列全体をスキャンし、B が空かどうかを確認します。空でない場合は、B スタックを置きます。要素が飛び出して A に入ります。現在空ではないので、最後のA スタックの要素は A: [3,5,2,3, ,*,7, , ]

したがって、A の最後の接尾辞は 3,5,2,3, となります。 ,*,7, ,

コンピュータはこれを取得したときにどのように計算しますか? プロセスは次のとおりです:
• 数値に遭遇すると、その数値はスタックに直接プッシュされます

演算子が見つかると、スタックの上位 2 つの要素が直接ポップアップされ、演算子によって計算され、結果がスタックにプッシュされます。手順 1 と 2 を実行します。最終的には、式の結果である要素のみが得られます。

練習しましょう:

1、数値に遭遇したとき3、5、2、3、スタックに直接プッシュ A[3 ,5,2,3]

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]

を押します。上記のことからわかるように、コンピュータにとって計算は簡単で、結果は次のとおりです。左から右にスキャンして取得します。

3 コードの実装

mid2post サフィックス式の検索

calcPostExp サフィックス式の評価の取得

cmpPriority 優先度の比較

//优先级
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;
}

Evaluate接尾辞式

vector<string> mid2post(string &str)
{

	vector<string>vstr;
	stack<char>cstack;
	for (int i = 0;i<str.size();++i)//扫描字符串
	{
		string temp = "";
		if (str[i] >= &#39;0&#39; && str[i] <= &#39;9&#39;)//若是数字
		{
			temp += str[i];
			while (i + 1<str.size() && str[i + 1] >= &#39;0&#39; && str[i + 1] <= &#39;9&#39;)
			{
				temp += str[i + 1];//若是连续数字
				++i;
			}
			vstr.push_back(temp);
		}
		else if (cstack.empty() || str[i] == &#39;(&#39;)//若栈空或者字符为&#39;(&#39;
			cstack.push(str[i]);
		else if (cmpPriority(cstack.top(), str[i]))//若栈顶元素优先级较高，栈顶元素出栈
		{
			if (str[i] == &#39;)&#39;)//若当前字符是右括号，栈中元素出栈，入字符串数组中，直到遇到&#39;(&#39;
			{
				while (!cstack.empty() && cstack.top() != &#39;(&#39;)
				{
					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;
}

接尾辞式を評価するには、演算子に基づいて主に 2 つの部分を取り出します

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] >= &#39;0&#39; && temp[0] <= &#39;9&#39;)//如果当前字符串是数字，利用字符串流转化为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 サイトの他の関連記事を参照してください。