이 기사에서는 접두사 식의 평가에 대해 논의할 것입니다.
접두사 표현식
이 표기법에서 연산자는 접두사입니다. 피연산자에, 즉 연산자는 피연산자보다 먼저 작성됩니다. 예:+ab . 이것은 중위 표기법 a + b와 동일합니다. . 접두사 표기법은 폴란드어 표기법이라고도 합니다. .
자세한 내용을 읽으십시오.
예:
* + 6 9 - 3 1
접두어 표현식은 중위 표현식보다 빠르게 평가됩니다. 또한 더 빠르게 평가할 수 있도록 접두사 표현식에 대괄호가 없습니다.
접두사 표현식을 평가하는 알고리즘:
접두사 표현식의 평가에는 스택 데이터 구조가 필요합니다. 연산자를 스택에 푸시한 다음 표현식을 풉니다.
표현의 각 요소를 하나씩 살펴보겠습니다. 현재 요소가 피연산자이면 스택에 푸시합니다. 그리고 그것이 연산자라면, 우리는 두 개의 피연산자를 팝하고, 연산을 수행하고, 피연산자 연산자 피연산자를 한 다음, 그 결과를 스택으로 다시 푸시합니다.
알고리즘 -
1단계: 표현식의 마지막 요소부터 시작합니다.
2단계: 현재 요소를 확인하십시오.
2.1단계: 피연산자이면 스택에 푸시합니다.
2.2단계: 연산자인 경우 스택에서 두 개의 피연산자를 팝합니다. 작업을 수행하고 요소를 스택으로 다시 푸시합니다.
3단계: 표현식의 모든 요소가 순회될 때까지 이 작업을 수행하고 연산의 결과가 될 스택의 맨 위를 반환합니다.
접두사 표현식을 해결하기 위한 알고리즘의 작동 방식을 살펴보겠습니다.
접두사 표현식:
* + 6 9 - 3 1
반복:1
스캔된 요소 => 1
작업 => 스택으로 푸시
스택 => 1
반복:2
스캔된 요소 => 3
작업 => 스택으로 푸시
스택 => 3, 1
반복:3
요소 스캔 => -
Operation => 스택에서 두 개를 꺼내서 연산을 수행하고 결과를 푸시합니다.
3 - 1 =2
스택 => 2
반복:4
요소 스캔 => 9
작업 => 스택으로 푸시
스택 => 9, 2
반복:5
스캔된 요소 => 6
작업 => 스택으로 푸시
스택 => 6, 9, 2
반복:6
요소 스캔 => +
Operation => 스택에서 두 개를 꺼내서 연산을 수행하고 결과를 푸시합니다.
6 + 9 =15
스택 => 15, 2
반복:7
요소 스캔 => *
Operation => 스택에서 두 개를 꺼내서 연산을 수행하고 결과를 푸시합니다.
15 * 2 =30
스택 => 30
End => 스택 맨 위로 반환, 결과 =30.
우리 솔루션의 작동을 설명하는 프로그램,
예
#include <bits/stdc++.h>
using namespace std;
double evaluatePrefix(string prefixExp) {
stack<double> operendStack;
int size = prefixExp.size() - 1;
for (int i = size; i >= 0; i--) {
if (isdigit(prefixExp[i]))
operendStack.push(prefixExp[i] - '0');
else {
double o1 = operendStack.top();
operendStack.pop();
double o2 = operendStack.top();
operendStack.pop();
if( prefixExp[i] == '+')
operendStack.push(o1 + o2);
else if( prefixExp[i] == '-')
operendStack.push(o1 - o2);
else if( prefixExp[i] == '*')
operendStack.push(o1 * o2);
else if( prefixExp[i] == '/')
operendStack.push(o1 / o2);
else{
cout<<"Invalid Expression";
return -1;
}
}
}
return operendStack.top();
}
int main()
{
string prefixExp = "*+69-31";
cout<<"The result of evaluation of expression "<<prefixExp<<" is "<<evaluatePrefix(prefixExp);
return 0;
} 출력 -
The result of evaluation of expression *+69-31 is 30