当前位置:网站首页>Reverse Polish notation
Reverse Polish notation
2022-07-05 13:02:00 【accumulate steadily ض】
The inverse Polish expression of stack application
What is the inverse Polish expression ??--> Source force buckle 150. Evaluate the inverse Polish expression
Reverse Polish notation :
The inverse Polish expression is a suffix expression , The so-called suffix means that the operator is written after .
The usual formula is a infix expression , Such as ( 1 + 2 ) * ( 3 + 4 ) .
The inverse Polish expression of the formula is written as ( ( 1 2 + ) ( 3 4 + ) * ) .
The inverse Polish expression has two main advantages :There is no ambiguity in the expression after removing the brackets , Even if the above formula is written as 1 2 + 3 4 + * You can also calculate the correct result according to the order .
It is suitable for stack operation : When it comes to numbers, it's on the stack ; When you encounter an operator, you take out two numbers at the top of the stack to calculate , And push the results into the stack
That is to say, we usually write correctly Addition, subtraction, multiplication and division of numbers , It's all like this .. For example : ( 1 + 2 ) * ( 3 + 4 )--> Infix expression , And we can make the computer understand ??-> This introduces today's inverse Polish expression, that is, the suffix expression , Let's turn infix expression into suffix expression .
for example :1+2*3+(4*2+5)*6
- Add curly braces to all operations
- Move the operator outside the corresponding bracket
- Remove all parentheses
Well, we get a suffix expression --> That is, the calculation that the computer can read
How does the computer calculate the result through such a suffix expression ???
That is our magical data structure --> Stack
- When encountering numbers, it will be added to the stack
- When you encounter an operator, you will get two numbers
- The first output is placed on the right side of the operator , The second time out is to the left of the release operator
- After the calculation, continue to put it on the stack
- The final stack top element is the result of the final expression calculation
Code implementation :
class Solution {
public int evalRPN(String[] tokens) {
// Ideas : When it comes to numbers, put them on the stack , If you encounter a number symbol, you will give two numbers to calculate
// Continue to stack the calculation results , Continue to traverse the end of the string
Stack<Integer> stack = new Stack<>();
for(int i =0;i<tokens.length;++i){
String str = tokens[i];
if(!isNumCharacter(str)){// Judge whether it is a symbol
// If it's a number, put it on the stack
int num = Integer.parseInt(str);
stack.push(num);
}else{
// If it's a character, pop the stack , Pop up two numbers
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();
}
// Used to determine whether this string is a character
public boolean isNumCharacter(String s){
if(s.equals("+")||s.equals("*")||
s.equals("-")||s.equals("/")){
return true;
}
return false;
}
}
边栏推荐
- 实现 1~number 之间,所有数字的加和
- Yyds dry inventory JS intercept file suffix
- Kotlin variable
- [Nacos cloud native] the first step of reading the source code is to start Nacos locally
- Concurrent performance test of SAP Spartacus with JMeter
- Vonedao solves the problem of organizational development effectiveness
- 事务的基本特性和隔离级别
- SAP UI5 DynamicPage 控件介紹
- RHCSA3
- JXL notes
猜你喜欢
关于 SAP UI5 floating footer 显示与否的单步调试以及使用 SAP UI5 的收益
Oppo Xiaobu launched Obert, a large pre training model, and promoted to the top of kgclue
Why is your next computer a computer? Explore different remote operations
How can non-technical departments participate in Devops?
将函数放在模块中
stirring! 2022 open atom global open source summit registration is hot!
SAP UI5 DynamicPage 控件介绍
CVPR 2022 | single step 3D target recognizer based on sparse transformer
2021-12-22 transaction record
Simply take stock reading notes (3/8)
随机推荐
ABAP editor in SAP segw transaction code
NFT: how to make money with unique assets?
RHCSA3
跨平台(32bit和64bit)的 printf 格式符 %lld 输出64位的解决方式
Leetcode20. Valid parentheses
RHCSA2
Compile kernel modules separately
Install rhel8.2 virtual machine
RHCSA1
由扫地增而引起的小叙
Default parameters of function & multiple methods of function parameters
Yyds dry inventory JS intercept file suffix
SAP UI5 DynamicPage 控件介紹
Kotlin function
函数传递参数小案例
Actual combat simulation │ JWT login authentication
RHCSA4
Distance measuring sensor chip 4530a used in home intelligent lighting
How to connect the API interface of Taobao open platform (super detailed)
【Nacos云原生】阅读源码第一步,本地启动Nacos