인스턴스 구문 분석 Java 중위 표현식 구현

이 기사에서는 산술 또는 논리식의 일반적인 표현 방법으로 중위 표현을 주로 소개하는 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)

대략적인 알고리즘은 다음 프로세스를 마스터합니다.

두 개의 스택을 준비합니다. 하나는 숫자 스택 A이고 다른 하나는 연산자 스택(+,-,*,/(,))B 등입니다.

1.0 숫자 스택 A의 경우 숫자가 발견되면 스택 A에 직접 푸시됩니다.

2.0 연산자 스택 B의 경우 여러 가지 상황이 있습니다.

2.1 '(' 연산자를 만나면 스택에 직접 푸시합니다.

2.2 ')' 연산자를 만나면 도착할 때까지 연산자 스택 B를 계속 팝합니다. )'. ('(' ~ ')' 사이에 팝된 연산자를 스택 A에 순서대로 밀어넣습니다.)

2.3 '+,-,*/'가 나타나면 현재 요소(현재 요소가 현재 요소라고 가정)와 스택 A의 연산을 비교합니다. top of stack B 기호의 우선순위(스택의 최상위 요소가 top이라고 가정)

2.3.1 top >= current인 경우 스택 B는 top < current가 루프를 종료할 때까지 루프에서 팝되고 비교됩니다.

2.3.2 top < current인 경우 current를 B 스택에 직접 넣습니다.

3.0 전체 문자열을 스캔하고 B 스택에 연산자가 있으면 스택에서 A로 팝합니다.

위의 알고리즘에 따라 3+(5*(2+ 3)+7의 과정)을 보여줍니다.

1, 3을 만나면 3은 스택 A에 들어갑니다. [3,]
2, +를 만나면, 스택 B [+,]
3에 들어가고, (를 만나면 스택 B [ +,(]
4에 들어가고, 5를 만나면 스택 A [3,5]
5에 들어가고, *를 만나면 우선 순위입니다. of *가 (보다 크면 스택 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에 넣습니다. 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,+, +

이것을 받으면 컴퓨터는 어떻게 계산할까요?

• 숫자를 만나면 스택에 직접 푸시됩니다. 연산자를 만나면 스택의 상위 두 요소를 직접 팝업하고 연산자를 통해 계산한 후 결과를 푸시합니다.
• 1단계와 2단계의 루프를 통해 계산하면 마지막으로 스택에 요소가 하나만 있게 되며 이는 표현식의 결과입니다.

연습해 보겠습니다.

1, 숫자를 만날 때 3,5,2,3, 스택 A[3,5,2,3]에 직접 푸시합니다.

2, +가 나타나면 스택 맨 위에서 2와 3을 팝업하고 합은 5입니다. . A[3,5,5]를 스택

3에 밀어넣고, *가 나타나면 스택 맨 위에서 5와 5를 팝업하고 합은 25가 됩니다. 7을 만나면 스택 A[3,25,7]
5에 직접 푸시하고, +를 만나면 스택 25,7의 상단을 팝업하고 최대 32를 더하고 스택 A[3,32]
에 푸시합니다. 6, +가 나타나면 스택의 상위 3개, 32개를 팝업하고 35까지 더한 다음 A[35]를 누릅니다.


위로부터 컴퓨터가 계산하기 쉽고 결과가 왼쪽에서 오른쪽으로 스캔하여 얻을 수 있습니다.

3 코드 구현

mid2post 접미사 표현식 찾기

calcPostExp 접미사 표현식 평가 얻기

cmp우선순위 우선순위 비교

//优先级
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] >= &#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;
}

서픽스 표현식 평가, 주로 두 개 꺼내기

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 중위 표현식 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!