当前位置:网站首页>逆波兰表达式
逆波兰表达式
2022-07-05 12:39:00 【厚积薄发ض】
栈的应用之逆波兰表达式
什么是逆波兰表达式呢??-->来源力扣150. 逆波兰表达式求值
逆波兰表达式:
逆波兰表达式是一种后缀表达式,所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式,如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点:去掉括号后表达式无歧义,上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算:遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中
也就是说我们平常写的对 数的加法减法乘法除法,都是这样的..的例如: ( 1 + 2 ) * ( 3 + 4 )-->中缀表达式,而我们这样能让计算机读懂呢??->这就引入了今天的逆波兰表达式也就是后缀表达式,我们就让中缀表达式转成后缀表达式。
例如:1+2*3+(4*2+5)*6
- 将所有运算都加上大括号
- 将运算符移动到对应括号的外面
- 去掉所有括号
好了我们就得到了一个后缀表达式-->也就是计算机能读懂的计算
那计算机是怎么通过这样的后缀表达式来计算出结果呢???
那就是我们这样神奇的数据结构-->栈
- 遇到数字就加入到栈中
- 遇到运算符就出两个数字
- 第一次出的放在运算符右边,第二次出的放运算符左边
- 计算完成之后继续放入栈中
- 最终栈顶元素就是最终表达式计算的结果
代码实现:
class Solution {
public int evalRPN(String[] tokens) {
//思路:遇到数字就入栈,如果遇到数字符号就出两个数进行计算
//计算结果继续入栈,一直遍历字符串结束
Stack<Integer> stack = new Stack<>();
for(int i =0;i<tokens.length;++i){
String str = tokens[i];
if(!isNumCharacter(str)){//判断是否是符号
//如果是数字的话就将其入栈
int num = Integer.parseInt(str);
stack.push(num);
}else{
//如果是字符就弹栈,弹出两个数字
int num2 = stack.pop();
int num1 = stack.pop();
switch(str){
case "+":
stack.push(num1+num2);
break;
case "-":
stack.push(num1-num2);
break;
case "*":
stack.push(num1*num2);
break;
case "/":
stack.push(num1/num2);
break;
}
}
}
return stack.peek();
}
//用来判断这个字符串是否是字符
public boolean isNumCharacter(String s){
if(s.equals("+")||s.equals("*")||
s.equals("-")||s.equals("/")){
return true;
}
return false;
}
}
边栏推荐
- Neural network of PRML reading notes (1)
- 超高效!Swagger-Yapi的秘密
- Full text search of MySQL
- About LDA model
- NLP engineer learning summary and index
- JSON parsing error special character processing (really speechless... Troubleshooting for a long time)
- Flume common commands and basic operations
- Simply take stock reading notes (4/8)
- Transactions from December 29, 2021 to January 4, 2022
- Distributed solution - Comprehensive decryption of distributed task scheduling platform - xxljob scheduling center cluster
猜你喜欢
Taobao product details API | get baby SKU, main map, evaluation and other API interfaces
Simply take stock reading notes (3/8)
实战模拟│JWT 登录认证
Pytoch implements tf Functions of the gather() function
Introduction to the principle of DNS
在家庭智能照明中应用的测距传感芯片4530A
Detailed structure and code of inception V3
Iterator details in list... Interview pits
Oppo Xiaobu launched Obert, a large pre training model, and promoted to the top of kgclue
你的下一台电脑何必是电脑,探索不一样的远程操作
随机推荐
Storage Basics
Using docker for MySQL 8.0 master-slave configuration
RHCSA1
Transactions from December 29, 2021 to January 4, 2022
滴滴开源DELTA:AI开发者可轻松训练自然语言模型
Taobao product details API | get baby SKU, main map, evaluation and other API interfaces
跨平台(32bit和64bit)的 printf 格式符 %lld 输出64位的解决方式
JDBC exercise - query data encapsulated into object return & simple login demo
The relationship between the size change of characteristic graph and various parameters before and after DL convolution operation
你的下一台电脑何必是电脑,探索不一样的远程操作
我在滴滴做开源
insmod 提示 Invalid module format
Distributed solution - completely solve website cross domain requests
Docker configures redis and redis clusters
Install rhel8.2 virtual machine
JSON parsing error special character processing (really speechless... Troubleshooting for a long time)
GPON technical standard analysis I
Laravel文档阅读笔记-mews/captcha的使用(验证码功能)
Didi open source Delta: AI developers can easily train natural language models
JDBC -- extract JDBC tool classes