经典白话算法之中缀表达式和后缀表达式

2024-02-19 03:32

本文主要是介绍经典白话算法之中缀表达式和后缀表达式,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、后缀表达式求值

后缀表达式也叫逆波兰表达式,其求值过程可以用到栈来辅助存储。

假定待求值的后缀表达式为:6  5  2  3  + 8 * + 3  +  *,则其求值过程如下:


(1)遍历表达式,遇到的数字首先放入栈中,依次读入6 5 2 3 此时栈如下所示:


(2)接着读到“+”,则从栈中弹出3和2,执行3+2,计算结果等于5,并将5压入到栈中。


(3)然后读到8(数字入栈),将其直接放入栈中。


(4)读到“*”,弹出8和5,执行8*5,并将结果40压入栈中。

而后过程类似,读到“+”,将40和5弹出,将40+5的结果45压入栈...以此类推。最后求的值288。


代码:

[cpp]  view plain copy
  1. #include<iostream>  
  2. #include<stack>  
  3. #include<stdio.h>  
  4. #include<string.h>  
  5. using namespace std;  
  6.   
  7. int main(){  
  8.     string PostArray;  
  9.     int len,i,a,b;  
  10.     while(cin>>PostArray){  
  11.         stack<int> Stack;  
  12.         len = PostArray.length();  
  13.         for(i = 0;i < len;i++){  
  14.             //跳过空格  
  15.             if(PostArray[i] == ' '){  
  16.                 continue;  
  17.             }  
  18.             //如果是数字则入栈  
  19.             if(PostArray[i] >= '0' && PostArray[i] <= '9'){  
  20.                 Stack.push(PostArray[i] - '0');  
  21.             }  
  22.             //如果是字符则从栈读出两个数进行运算  
  23.             else{  
  24.                 //算数a出栈  
  25.                 a = Stack.top();  
  26.                 Stack.pop();  
  27.                 //算法b出栈  
  28.                 b = Stack.top();  
  29.                 Stack.pop();  
  30.                 //进行运算(+ - * /)  
  31.                 if(PostArray[i] == '+'){  
  32.                     Stack.push(a + b);  
  33.                 }  
  34.                 else if(PostArray[i] == '-'){  
  35.                     Stack.push(a - b);  
  36.                 }  
  37.                 else if(PostArray[i] == '*'){  
  38.                     Stack.push(a * b);  
  39.                 }  
  40.                 else if(PostArray[i] == '/'){  
  41.                     Stack.push(a / b);  
  42.                 }  
  43.             }  
  44.         }//for  
  45.         printf("%d\n",Stack.top());  
  46.     }//while  
  47.     return 0;  
  48. }  

这篇关于经典白话算法之中缀表达式和后缀表达式的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/723366

相关文章

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

使用C#代码计算数学表达式实例

《使用C#代码计算数学表达式实例》这段文字主要讲述了如何使用C#语言来计算数学表达式,该程序通过使用Dictionary保存变量,定义了运算符优先级,并实现了EvaluateExpression方法来... 目录C#代码计算数学表达式该方法很长,因此我将分段描述下面的代码片段显示了下一步以下代码显示该方法如

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

Python在固定文件夹批量创建固定后缀的文件(方法详解)

《Python在固定文件夹批量创建固定后缀的文件(方法详解)》文章讲述了如何使用Python批量创建后缀为.md的文件夹,生成100个,代码中需要修改的路径、前缀和后缀名,并提供了注意事项和代码示例,... 目录1. python需求的任务2. Python代码的实现3. 代码修改的位置4. 运行结果5.

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个