Implémentation d'instances d'analyse d'expressions d'infixe Java

Cet article vous apporte des connaissances pertinentes sur java, qui présente principalement l'expression infixe comme méthode d'expression générale de formules arithmétiques ou logiques. Les expressions infixes ne sont pas facilement analysées par les ordinateurs, mais sont toujours utilisées par de nombreux langages de programmation car elles sont conformes à l'usage humain courant. Jetons-y un coup d'œil ensemble, j'espère que cela sera utile à tout le monde.

Apprentissage recommandé : "Tutoriel vidéo Java"

1. Concept

Qu'est-ce qu'une expression infixe et qu'est-ce qu'une expression suffixe ?

Les quatre opérations arithmétiques que vous avez apprises depuis l'école primaire, par exemple : 3+( 5*(2+3)+7) Une expression comme celle-ci est une expression infixe. Les expressions infixes sont faciles à comprendre pour le cerveau humain, et la priorité de chaque opérateur est également facile à juger pour le cerveau humain. Calculez d'abord celles entre parenthèses, puis *, puis +, -

, mais ce type d'expression est. très défavorable aux ordinateurs, convertissez en quelque sorte l'expression de préfixe en expression de suffixe pour faciliter le calcul informatique. Par exemple, l'expression de suffixe de 3+(5*(2+3)+7) est 3,5,2, 3,+,* ,7,+, +. Cette expression est facile à calculer pour les ordinateurs. Pourquoi est-elle facile à calculer grâce au flux d'algorithmes 2, vous aurez une compréhension approfondie.

2. Processus d'algorithme

Comment convertir une expression infixe en expression postfixe ? Par exemple, quel est le processus de conversion de 3+(5*(2+3)+7) en expression postfixe ?

Priorité de l'opérateur :

• +, - est inférieur à *, /
• + est égal à -
• * est égal à /

Les parenthèses gauches et droites sont traitées comme des opérateurs spéciaux. (Si vous rencontrez '(', vous n'avez pas besoin de juger de la priorité et allez directement à la pile d'opérateurs ; si vous rencontrez ')', vous n'avez pas besoin de juger de la priorité et vous sortez directement de l'opérateur pile)

L'algorithme approximatif maîtrise les processus suivants :

Préparez deux piles, l'une est la pile de nombres A, l'autre est la pile d'opérateurs (+,-,*,/(,))B, etc.

1.0 Pour la pile de numéros A, lorsqu'un nombre est rencontré, il est directement poussé dans la pile A.

2.0 Pour la pile d'opérateurs B, il existe plusieurs situations

2.1 Lorsque vous rencontrez l'opérateur '(', poussez-le directement sur la pile

2.2 Lorsque vous rencontrez l'opérateur ')', continuez à faire éclater la pile d'opérateur B jusqu'à ce qu'elle rencontre' )'. (Poussez les opérateurs sautés entre '(' à ')' dans la pile A dans l'ordre)

2.3 Lorsque vous rencontrez '+,-,*/', comparez l'élément actuel (en supposant que l'élément actuel est actuel) avec l'opération sur le top of stack B La priorité du symbole (en supposant que l'élément supérieur de la pile est top).

2.3.1 Si top >= current, la pile B est sautée et comparée dans une boucle jusqu'à ce que top < et le courant est poussé sur la pile

2.3.2 Si le niveau supérieur <

Suivez l'algorithme ci-dessus pour démontrer 3+(5*(2+ Le processus de 3)+7) :

1, lorsqu'il rencontre 3, 3 va dans la pile A [3,]

2, lorsqu'il rencontre +, il va dans la pile B [+,]

3, lorsqu'il rencontre (, il entre dans la pile B [ +,(]
4, lorsqu'il rencontre 5, poussez-le dans la pile A [3,5]
5, lorsque en rencontrant *, la priorité de * est supérieure à (, poussez dans la pile B [+,(,*]
6, en rencontrant (, allez dans la pile B [+,(,*,(]
7, rencontre 2, allez vers la pile A [3,5,2]
8, rencontrez +, allez dans la pile B [+,(,*,(,+]
9, lorsque vous rencontrez 3, poussez-le dans la pile A [3,5,2, 3]
10, lorsque vous rencontrez ), faites apparaître la pile B, allez directement à '(' et placez l'opérateur sauté dans la pile A. B:[ +, (,*] A:[3,5,2,3, +]
11, lorsque + est rencontré, la priorité de + est plus petite que l'élément supérieur * de B, donc * fait apparaître la pile de B, la place dans A et met + dans B. B:[ +,(, +] A :[3,5,2,3,+,*]
12, rencontre 7, mettre dans la pile A [3,5,2,3,+,*,7 ]
13, lors de la rencontre), pop la pile B, allez directement à '(' et placez l'opérateur sauté dans la pile A. B:[ +] A:[3,5,2,3,+,*,7,+ ]
14, scannez le chaîne entière et déterminez si B est vide. S'il n'est pas vide, insérez l'élément de la pile B dans A. Il n'est actuellement pas vide, donc le dernier élément de la pile A est A : [3,5,2, 3,+. ,*,7,+, +]

Donc l'expression du suffixe final de A est 3,5,2,3,+,*,7,+, +

Comment l'ordinateur calculera-t-il lorsqu'il obtiendra cela ? Le processus est le suivant :

Lorsqu'il rencontre un nombre, il est poussé directement dans la pile. Lorsqu'il rencontre un opérateur, il fait directement apparaître les deux éléments supérieurs de la pile, le calcule via l'opérateur et pousse le. résultat sur la pile.

• Calcule à travers la boucle des étapes 1 et 2, et enfin Il n'y aura qu'un seul élément dans la pile, et voici le résultat de l'expression
• Pratirons-le :

1, quand rencontrant les nombres 3,5,2,3, poussez-le directement dans la pile A[3,5,2,3].

2, lorsque + est rencontré, faites apparaître 2 et 3 du haut de la pile, et le la somme est 5. Poussez A[3,5,5] sur la pile

3, lorsque * est rencontré, faites apparaître 5 et 5 du haut de la pile, et la somme est 25. Poussez A[ 3,25]

4, lorsque vous rencontrez 7, poussez directement dans la pile A[3,25,7]

5, lorsque vous rencontrez +, faites apparaître le haut de la pile 25,7, additionnez jusqu'à 32, poussez dans la pile A[3, 32]
6, lorsque + est rencontré, affichez les 3 premiers, 32 de la pile, et additionnez jusqu'à 35. Appuyez sur A[35]


De ce qui précède, nous pouvons savoir que l'ordinateur est facile à calculer, et le résultat peut être obtenu en scannant de gauche à droite.

3 implémentations de code

mid2post pour trouver l'expression du suffixe

calcPostExp pour obtenir l'évaluation de l'expression du suffixe

Comparaison des priorités 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;
}

pour trouver l'évaluation de l'expression du suffixe

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;
}

pour évaluer l'expression du suffixe, principalement en retirer deux

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();//最终的栈顶元素就是求解的结果
}

basé sur l'opérateur. Apprentissage recommandé : "

tutoriel vidéo Java

"

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!