网站系统性能定义,白城做网站,珠宝设计制作培训,建站平台在线提交表格功能目录
前言
一#xff0c;前缀中缀后缀的基本概念
二#xff0c;前缀与后缀表达式
三#xff0c;使用栈实现后缀
四#xff0c;由中缀到后缀
总结 前言
这里学习前缀中缀后缀为我们学习树和图做准备#xff0c;这个主题主要是对于算术和逻辑表达式求值#xff0c;这…目录
前言
一前缀中缀后缀的基本概念
二前缀与后缀表达式
三使用栈实现后缀
四由中缀到后缀
总结 前言
这里学习前缀中缀后缀为我们学习树和图做准备这个主题主要是对于算术和逻辑表达式求值这个还可以用于算法因为这个可以提高效率节省时间 一前缀中缀后缀的基本概念 如何撰写一个表达式 这个式我们描述一个表达式的过程这个中间为一个操作符这个旁边式操作数 就好比如中间的符号就是操作符旁边的数字就是操作数 操作符的优先级 1括号( ) { } [ ] 2幂运算如果是2^5^6这个是先从最右边运算把5的6次方算出来然后再计算2的3125次方 3乘除法从左到右 4加减法从左到右 中缀表达式1先看优先级 2再看同优先级的操作符之间的冲突 3再来看结合律 但是中缀表达式就是需要括号来规定有限级顺序要不然有时候会得不到自己想要的答案很容易犯优先级错误而且因为加了括号计算机程序需要考虑有限级的问题会使计算机效率下降所以还有不考虑优先级顺序的这个就是前缀表达式和后缀表达式 二前缀与后缀表达式 前缀表达式prefix 中缀表达式infix 后缀表达式profix 前缀表达式 infix prefix 2323p-q-pqab*ca*bc 前缀表达式相比中缀表达式就更快一点不需要考虑优先级问题效率更高计算机自行会处理这个表达式 后缀表达式 prefixproefix2323p-q pq- ab*cabc* 前缀后缀的理解 这里可能会有点懵逼那我们把这个式子拆开去理解 前缀后缀 我们不难发现中缀相对我们容易理解一些但是效率较低就是可读性高 前缀和后缀就是可读性差了但是计算机的效率高 但是为什么还有前缀后缀呢我们不是要一个就好了吗其实后缀的效率相比前缀高 后缀表达式 后缀表达式的计算过程非常直观从左到右扫描表达式遇到操作数就压入栈遇到操作符就从栈中弹出操作数进行计算然后将结果压入栈。 这种计算方式非常适合计算机实现因为栈的操作压栈和弹栈非常高效且不需要额外的逻辑来处理操作符优先级。 前缀表达式 前缀表达式的计算需要从右向左扫描这在实现上不如从左到右扫描直观。 每次遇到操作符时需要确定其操作数的范围这可能需要额外的逻辑来处理嵌套结构增加了计算复杂度。 所以我们在使用的时候一般都是用后缀表达式不是用前缀表达式 三使用栈实现后缀 我们以23*54*9-为例子来写写后缀的程序 思路 第一代代码实现 #include iostream
#include stack
#include string
/*提供string类型提供length()计算字符串长度提供stoi()函数是把字符串的数字展示出来其他弄掉
*/
#include sstream
#include cctype
/*提供isdigit函数 检查是否为字符*/using namespace std;// 函数用于从字符串中提取操作数
int getOperand(const string expr, int index) {string operand;while (index expr.length() isdigit(expr[index])) {operand expr[index];}return stoi(operand);
}// 函数用于计算后缀表达式的值
int evaluatePostfix(const string expr) {stackints;int index 0;while (index expr.length()) {if (isdigit(expr[index])) {// 如果是操作数压入栈中s.push(getOperand(expr, index));}else {// 如果是操作符弹出两个操作数进行计算int operand2 s.top();s.pop();int operand1 s.top();s.pop();switch (expr[index]) {case : s.push(operand1 operand2); break;case -: s.push(operand1 - operand2); break;case *: s.push(operand1 * operand2); break;case /: s.push(operand1 / operand2); break;}}index;}// 栈顶元素即为最终结果return s.top();
}int main() {string postfixExpr 23*54*;cout 后缀表达式的计算结果为: evaluatePostfix(postfixExpr) endl;return 0;
} 我们执行这个代码的时候运行这个23*54*的结果为77运行结果是错的为什么呢我们通过监视来看看怎么回事 我们会发现这个是把23和54压进去了然后把23和54进行相加所以实现错了这里是需要我们逐个逐个输入到栈里面而不是一次性输入 string库函数 提供string类型 提供length()计算字符串长度 提供stoi()函数是把字符串的数字展示出来其他弄掉 小技巧这里可以利用s.c来监视这个栈里面的各个值因为这个是底层容器这里细讲就涉及的比较多了等作者学完stl库然后也会发文章讲述 所以目前的问题是解决这个逐个输入的问题 第二代代码 #include iostream
#include stack
#include sstream
#include stringusing namespace std;int evaluatePostfix(const string expr) {stackint s;stringstream ss(expr); //这个就是为一个类似cin作用的类型string token;while (ss token) {if (isdigit(token[0])) {s.push(stoi(token)); // 读取完整的数字}else {int operand2 s.top(); s.pop();int operand1 s.top(); s.pop();switch (token[0]) {case : s.push(operand1 operand2); break;case -: s.push(operand1 - operand2); break;case *: s.push(operand1 * operand2); break;case /: s.push(operand1 / operand2); break;}}}return s.top();
}int main() {string postfixExpr 2 3 * 5 4 * ; // 需要空格分隔cout 后缀表达式的计算结果为: evaluatePostfix(postfixExpr) endl;return 0;
} 这里我们就是要输入的时候要注意空格的输入 stringstream ss(expr); 这一行的作用是使用 stringstream 来解析字符串 expr使其能够像读取输入流cin一样逐个提取单词或数字。 详细解析 stringstream 是 C 标准库中的一个工具它允许将字符串作为输入流来处理stringstream ss(expr); 创建一个 stringstream 对象 ss并用 expr 进行初始化在 while (ss token) 这行代码中ss token 逐个读取 expr 中的单词用空格分隔存入 token 变量中 这里就是一个流这里的可以理解为从这个流里面取字符提取出来更cout里用法一样的意思然后识别的到空格或者换行等就会停止当前识别然后在继续识别这流里面的字符串然后用if-else语句来判断是数字和符号这样就可以判断是否为弹出或者压栈 总结我们利用了一个string类型存储这个后缀的字符串但是要用空格空出对应的数字与符号然后放入到流里面用法stringstream 名字(对应的字符串)然后利用操作数来进行编写 前缀也就是同样的写法这里留给读者自己编写 四由中缀到后缀 这里直接包含括号直接一步到位但是我们先谈谈这个思路 以AB*C-D*E为例子 这个思路主要是优先级问题遇到优先级比栈里面小的话就直接弹出来 但是我们由括号呢 这里的代码就先不展示了后续根据需求写 总结
根据这篇文章我们了解了前缀中缀后缀这些东西这些东西是可以帮助我们以后再算法里面是追求可读性还是效率作为一个很好的基础然后我们运用了栈和C来实现了后缀的实现这样我们就可以更好掌握stl里面栈的使用了和计算机是如何计算这个后缀表达式的
