数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中的前缀表达式的求值
在本文中，我们将讨论前缀表达式的求值。
前缀表达式
在这种表示法中，运算符位于操作数之前，即运算符写在操作数前面。例如，+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
扫描的元素 => -
操作 => 从栈中弹出两个元素，执行运算并将结果压回栈中。
3 - 1 = 2
栈=> 2
迭代：4
扫描的元素 => 9
操作 => 压入栈
栈=> 9 , 2
迭代：5
扫描的元素 => 6
操作 => 压入栈
栈=> 6, 9 , 2
迭代：6
扫描的元素 => +
操作 => 从栈中弹出两个元素，执行运算并将结果压回栈中。
6 + 9 = 15
栈 => 15 , 2
迭代：7
扫描的元素 => *
操作 => 从栈中弹出两个元素，执行运算并将结果压回栈中。
15 * 2 = 30
栈=> 30
结束 => 返回栈顶元素，结果 = 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
14K+ 次浏览
