当前位置:网站首页>Prefix, infix, suffix expression "recommended collection"
Prefix, infix, suffix expression "recommended collection"
2022-07-05 13:30:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm your friend, Quan Jun .
keyword : Concept , Prefix expression , Prefix notation , Infix expression , Infix notation , Polish style , Postfix expression , Suffix notation , Reverse Polish
They are all notations of expressions , Therefore, it is also called prefix notation 、 Infix notation and suffix notation . The difference between them lies in the position of the operator relative to the operand : The operator of the prefix expression precedes its associated operand ; Infix and suffix are the same .
give an example : (3 + 4) × 5 – 6 Infix expression – × + 3 4 5 6 Prefix expression 3 4 + 5 × 6 – Postfix expression
Infix expression ( Infix notation ) Infix expression is a general expression of arithmetic or logic formula , The operator is in the middle of the operand in the form of infix . Infix expression is a common arithmetic expression . Although the human brain can easily understand and analyze infix expressions , But for computers, infix expressions are very complex , Therefore, when calculating the value of an expression , Usually you need to convert infix expression into prefix or suffix expression first , Then evaluate . For a computer , Calculating the value of a prefix or suffix expression is very simple .
Prefix expression ( Prefix notation 、 Polish style ) The operator of the prefix expression precedes the operands .
Computer evaluation of prefix expressions : Scan expressions from right to left , When it comes to numbers , Push numbers onto the stack , When an operator is encountered , Pop up the two numbers at the top of the stack , Use operators to evaluate them ( Top element of stack op Subpop element ), And stack the results ; Repeat until the left end of the expression , The final value is the result of the expression . For example, prefix expression “- × + 3 4 5 6”: (1) Scan right to left , take 6、5、4、3 Push into the stack ; (2) encounter + Operator , So pop up 3 and 4(3 For the stack top element ,4 Is the secondary top element , Note the comparison with the suffix expression ), To calculate the 3+4 Value , have to 7, then 7 Push ; (3) Next is × Operator , So pop up 7 and 5, To calculate the 7×5=35, take 35 Push ; (4) And finally - Operator , To calculate the 35-6 Value , namely 29, The final result is . It can be seen that , It's easy to calculate the value of prefix expression by computer .
Converts an infix expression to a prefix expression : Follow these steps : (1) Initialize two stacks : Operator stack S1 And a stack for storing intermediate results S2; (2) Scan infix expressions from right to left ; (3) When it comes to operands , Press it in S2; (4) When an operator is encountered , Compare it with S1 The priority of the top of stack operator : (4-1) If S1 It's empty , Or the top of the stack operator is the right bracket “)”, This operator will be put on the stack directly ; (4-2) otherwise , If the priority is higher than or equal to the top of the stack operator , Also push operators into S1; (4-3) otherwise , take S1 The operator at the top of the stack pops up and pushes into S2 in , Turn again (4-1) And S1 Compared with the new stack top operators in ; (5) When brackets are encountered : (5-1) If it's right bracket “)”, Press in directly S1; (5-2) If it's left parenthesis “(”, Then it pops up in turn S1 The operator at the top of the stack , And press in S2, Until you meet the right bracket , This pair of parentheses is discarded ; (6) Repeat step (2) to (5), To the far left of the expression ; (7) take S1 The rest of the operators in the pop-up and press in S2; (8) Pop up one by one S2 And output , The result is the prefix expression corresponding to infix expression . for example , The infix expression “1+((2+3)×4)-5” The process of converting to prefix expression is as follows :
Scanned elements | S2( At the bottom of the stack -> To the top of the stack ) | S1 ( At the bottom of the stack -> To the top of the stack ) | explain |
---|---|---|---|
5 | 5 | empty | Numbers , Direct stack |
– | 5 | – | S1 It's empty , Operators are put directly on the stack |
) | 5 | – ) | The right bracket is directly put on the stack |
4 | 5 4 | – ) | The numbers go straight to the stack |
× | 5 4 | – ) × | S1 The top of the stack is the right parenthesis , Direct stack |
) | 5 4 | – ) × ) | The right bracket is directly put on the stack |
3 | 5 4 3 | – ) × ) | Numbers |
+ | 5 4 3 | – ) × ) + | S1 The top of the stack is the right parenthesis , Direct stack |
2 | 5 4 3 2 | – ) × ) + | Numbers |
( | 5 4 3 2 + | – ) × | Left parenthesis , Pop up the operator until you encounter the closing bracket |
( | 5 4 3 2 + × | – | ditto |
+ | 5 4 3 2 + × | – + | Priority and - identical , Push |
1 | 5 4 3 2 + × 1 | – + | Numbers |
Get to the far left | 5 4 3 2 + × 1 + – | empty | S1 The remaining operators in |
So the result is “- + 1 × + 2 3 4 5”.
Postfix expression ( Suffix notation 、 Reverse Polish )
The suffix expression is similar to the prefix expression , Just the operator after the operand .
Computer evaluation of suffix expressions : Similar to prefix expressions , It's just that the order is from left to right : Scan expressions from left to right , When it comes to numbers , Push numbers onto the stack , When an operator is encountered , Pop up the two numbers at the top of the stack , Use operators to evaluate them ( Subpop element op Top element of stack ), And stack the results ; Repeat until the right end of the expression , The final value is the result of the expression . For example, suffix expressions “3 4 + 5 × 6 -”: (1) Scan from left to right , take 3 and 4 Push into the stack ; (2) encounter + Operator , So pop up 4 and 3(4 For the stack top element ,3 Is the secondary top element , Note the comparison with the prefix expression ), To calculate the 3+4 Value , have to 7, then 7 Push ; (3) take 5 Push ; (4) Next is × Operator , So pop up 5 and 7, To calculate the 7×5=35, take 35 Push ; (5) take 6 Push ; (6) And finally - Operator , To calculate the 35-6 Value , namely 29, The final result is .
Convert infix expression to suffix expression : Similar to converting to a prefix expression , Follow these steps : (1) Initialize two stacks : Operator stack S1 And a stack for storing intermediate results S2; (2) Scan infix expressions from left to right ; (3) When it comes to operands , Press it in S2; (4) When an operator is encountered , Compare it with S1 The priority of the top of stack operator : (4-1) If S1 It's empty , Or stack top operator is left bracket “(”, This operator will be put on the stack directly ; (4-2) otherwise , If the priority is higher than the top of the stack operator , Also push operators into S1( Note that the conversion to prefix expression has higher priority or the same , And this doesn't include the same situation ); (4-3) otherwise , take S1 The operator at the top of the stack pops up and pushes into S2 in , Turn again (4-1) And S1 Compared with the new stack top operators in ; (5) When brackets are encountered : (5-1) If it's left parenthesis “(”, Press in directly S1; (5-2) If it's right bracket “)”, Then it pops up in turn S1 The operator at the top of the stack , And press in S2, Until we meet the left bracket , This pair of parentheses is discarded ; (6) Repeat step (2) to (5), Up to the far right of the expression ; (7) take S1 The rest of the operators in the pop-up and press in S2; (8) Pop up one by one S2 And output , The reverse order of the result is the suffix expression corresponding to the infix expression ( Do not reverse the order when converting to prefix expressions ). for example , The infix expression “1+((2+3)×4)-5” The process of converting to a suffix expression is as follows :
Scanned elements | S2( At the bottom of the stack -> To the top of the stack ) | S1 ( At the bottom of the stack -> To the top of the stack ) | explain |
---|---|---|---|
1 | 1 | empty | Numbers , Direct stack |
+ | 1 | + | S1 It's empty , Operators are put directly on the stack |
( | 1 | + ( | Left parenthesis , Direct stack |
( | 1 | + ( ( | ditto |
2 | 1 2 | + ( ( | Numbers |
+ | 1 2 | + ( ( + | S1 The top of the stack is left bracket , Operators are put directly on the stack |
3 | 1 2 3 | + ( ( + | Numbers |
) | 1 2 3 + | + ( | Right bracket , Pop up the operator until the left bracket is encountered |
× | 1 2 3 + | + ( × | S1 The top of the stack is left bracket , Operators are put directly on the stack |
4 | 1 2 3 + 4 | + ( × | Numbers |
) | 1 2 3 + 4 × | + | Right bracket , Pop up the operator until the left bracket is encountered |
– | 1 2 3 + 4 × + | – | - And + Same priority , So pop up +, Recompression - |
5 | 1 2 3 + 4 × + 5 | – | Numbers |
To the far right | 1 2 3 + 4 × + 5 – | empty | S1 The remaining operators in |
So the result is “1 2 3 + 4 × + 5 -”( Note that you need to output in reverse order ).
To write Java The program converts an infix expression into a prefix expression and a suffix expression , And compute the value of the expression . Among them toPolishNotation() Method to convert infix expression to prefix expression ( Polish style )、toReversePolishNotation() Method is used to convert infix expression to suffix expression ( Reverse Polish ):
notes : (1) The program is very long and there are few comments , But if you understand the above theoretical content, then compile and run the program , It's easier to understand . If you have patience, you can study .(2) This program is written by the author to illustrate the above concepts , Only a simple test was done , There is no guarantee that Bug, So don't use it for other occasions besides research .
package qmk.simple_test;
import java.util.Scanner;
import java.util.Stack;
/**
* Example of converting an infix-expression to
* Polish Notation (PN) or Reverse Polish Notation (RPN).
* Written in 2011-8-25
* @author QiaoMingkui
*/
public class Calculator {
public static final String USAGE = "== usage ==\n"
+ "input the expressions, and then the program "
+ "will calculate them and show the result.\n"
+ "input 'bye' to exit.\n";
/**
* @param args
*/
public static void main(String[] args) {
System.out.println(USAGE);
Scanner scanner = new Scanner(System.in);
String input = "";
final String CLOSE_MARK = "bye";
System.out.println("input an expression:");
input = scanner.nextLine();
while (input.length() != 0
&& !CLOSE_MARK.equals((input))) {
System.out.print("Polish Notation (PN):");
try {
toPolishNotation(input);
} catch (NumberFormatException e) {
System.out.println("\ninput error, not a number.");
} catch (IllegalArgumentException e) {
System.out.println("\ninput error:" + e.getMessage());
} catch (Exception e) {
System.out.println("\ninput error, invalid expression.");
}
System.out.print("Reverse Polish Notation (RPN):");
try {
toReversePolishNotation(input);
} catch (NumberFormatException e) {
System.out.println("\ninput error, not a number.");
} catch (IllegalArgumentException e) {
System.out.println("\ninput error:" + e.getMessage());
} catch (Exception e) {
System.out.println("\ninput error, invalid expression.");
}
System.out.println("input a new expression:");
input = scanner.nextLine();
}
System.out.println("program exits");
}
/**
* parse the expression , and calculate it.
* @param input
* @throws IllegalArgumentException
* @throws NumberFormatException
*/
private static void toPolishNotation(String input)
throws IllegalArgumentException, NumberFormatException {
int len = input.length();
char c, tempChar;
Stack<Character> s1 = new Stack<Character>();
Stack<Double> s2 = new Stack<Double>();
Stack<Object> expression = new Stack<Object>();
double number;
int lastIndex = -1;
for (int i=len-1; i>=0; --i) {
c = input.charAt(i);
if (Character.isDigit(c)) {
lastIndex = readDoubleReverse(input, i);
number = Double.parseDouble(input.substring(lastIndex, i+1));
s2.push(number);
i = lastIndex;
if ((int) number == number)
expression.push((int) number);
else
expression.push(number);
} else if (isOperator(c)) {
while (!s1.isEmpty()
&& s1.peek() != ')'
&& priorityCompare(c, s1.peek()) < 0) {
expression.push(s1.peek());
s2.push(calc(s2.pop(), s2.pop(), s1.pop()));
}
s1.push(c);
} else if (c == ')') {
s1.push(c);
} else if (c == '(') {
while ((tempChar=s1.pop()) != ')') {
expression.push(tempChar);
s2.push(calc(s2.pop(), s2.pop(), tempChar));
if (s1.isEmpty()) {
throw new IllegalArgumentException(
"bracket dosen't match, missing right bracket ')'.");
}
}
} else if (c == ' ') {
// ignore
} else {
throw new IllegalArgumentException(
"wrong character '" + c + "'");
}
}
while (!s1.isEmpty()) {
tempChar = s1.pop();
expression.push(tempChar);
s2.push(calc(s2.pop(), s2.pop(), tempChar));
}
while (!expression.isEmpty()) {
System.out.print(expression.pop() + " ");
}
double result = s2.pop();
if (!s2.isEmpty())
throw new IllegalArgumentException("input is a wrong expression.");
System.out.println();
if ((int) result == result)
System.out.println("the result is " + (int) result);
else
System.out.println("the result is " + result);
}
/**
* parse the expression, and calculate it.
* @param input
* @throws IllegalArgumentException
* @throws NumberFormatException
*/
private static void toReversePolishNotation(String input)
throws IllegalArgumentException, NumberFormatException {
int len = input.length();
char c, tempChar;
Stack<Character> s1 = new Stack<Character>();
Stack<Double> s2 = new Stack<Double>();
double number;
int lastIndex = -1;
for (int i=0; i<len; ++i) {
c = input.charAt(i);
if (Character.isDigit(c) || c == '.') {
lastIndex = readDouble(input, i);
number = Double.parseDouble(input.substring(i, lastIndex));
s2.push(number);
i = lastIndex - 1;
if ((int) number == number)
System.out.print((int) number + " ");
else
System.out.print(number + " ");
} else if (isOperator(c)) {
while (!s1.isEmpty()
&& s1.peek() != '('
&& priorityCompare(c, s1.peek()) <= 0) {
System.out.print(s1.peek() + " ");
double num1 = s2.pop();
double num2 = s2.pop();
s2.push(calc(num2, num1, s1.pop()));
}
s1.push(c);
} else if (c == '(') {
s1.push(c);
} else if (c == ')') {
while ((tempChar=s1.pop()) != '(') {
System.out.print(tempChar + " ");
double num1 = s2.pop();
double num2 = s2.pop();
s2.push(calc(num2, num1, tempChar));
if (s1.isEmpty()) {
throw new IllegalArgumentException(
"bracket dosen't match, missing left bracket '('.");
}
}
} else if (c == ' ') {
// ignore
} else {
throw new IllegalArgumentException(
"wrong character '" + c + "'");
}
}
while (!s1.isEmpty()) {
tempChar = s1.pop();
System.out.print(tempChar + " ");
double num1 = s2.pop();
double num2 = s2.pop();
s2.push(calc(num2, num1, tempChar));
}
double result = s2.pop();
if (!s2.isEmpty())
throw new IllegalArgumentException("input is a wrong expression.");
System.out.println();
if ((int) result == result)
System.out.println("the result is " + (int) result);
else
System.out.println("the result is " + result);
}
/**
* calculate the two number with the operation.
* @param num1
* @param num2
* @param op
* @return
* @throws IllegalArgumentException
*/
private static double calc(double num1, double num2, char op)
throws IllegalArgumentException {
switch (op) {
case '+':
return num1 + num2;
case '-':
return num1 - num2;
case '*':
return num1 * num2;
case '/':
if (num2 == 0) throw new IllegalArgumentException("divisor can't be 0.");
return num1 / num2;
default:
return 0; // will never catch up here
}
}
/**
* compare the two operations' priority.
* @param c
* @param peek
* @return
*/
private static int priorityCompare(char op1, char op2) {
switch (op1) {
case '+': case '-':
return (op2 == '*' || op2 == '/' ? -1 : 0);
case '*': case '/':
return (op2 == '+' || op2 == '-' ? 1 : 0);
}
return 1;
}
/**
* read the next number (reverse)
* @param input
* @param start
* @return
* @throws IllegalArgumentException
*/
private static int readDoubleReverse(String input, int start)
throws IllegalArgumentException {
int dotIndex = -1;
char c;
for (int i=start; i>=0; --i) {
c = input.charAt(i);
if (c == '.') {
if (dotIndex != -1)
throw new IllegalArgumentException(
"there have more than 1 dots in the number.");
else
dotIndex = i;
} else if (!Character.isDigit(c)) {
return i + 1;
} else if (i == 0) {
return 0;
}
}
throw new IllegalArgumentException("not a number.");
}
/**
* read the next number
* @param input
* @param start
* @return
* @throws IllegalArgumentException
*/
private static int readDouble(String input, int start)
throws IllegalArgumentException {
int len = input.length();
int dotIndex = -1;
char c;
for (int i=start; i<len; ++i) {
c = input.charAt(i);
if (c == '.') {
if (dotIndex != -1)
throw new IllegalArgumentException(
"there have more than 1 dots in the number.");
else if (i == len - 1)
throw new IllegalArgumentException(
"not a number, dot can't be the last part of a number.");
else
dotIndex = i;
} else if (!Character.isDigit(c)) {
if (dotIndex == -1 || i - dotIndex > 1)
return i;
else
throw new IllegalArgumentException(
"not a number, dot can't be the last part of a number.");
} else if (i == len - 1) {
return len;
}
}
throw new IllegalArgumentException("not a number.");
}
/**
* return true if the character is an operator.
* @param c
* @return
*/
private static boolean isOperator(char c) {
return (c=='+' || c=='-' || c=='*' || c=='/');
}
}
Here are the results of the program ( Green is user input ):
== usage ==
input the expressions, and then the program will calculate them and show the result.
input ‘bye’ to exit.
input an expression:
3.8+5.3
Polish Notation (PN):+ 3.8 5.3
the result is 9.1
Reverse Polish Notation (RPN):3.8 5.3 +
the result is 9.1
input a new expression:
5*(9.1+3.2)/(1-5+4.88)
Polish Notation (PN):/ * 5 + 9.1 3.2 + – 1 5 4.88
the result is 69.88636363636364
Reverse Polish Notation (RPN):5 9.1 3.2 + * 1 5 – 4.88 + /
the result is 69.88636363636364
input a new expression:
1+((2+3)*4)-5
Polish Notation (PN):- + 1 * + 2 3 4 5
the result is 16
Reverse Polish Notation (RPN):1 2 3 + 4 * + 5 –
the result is 16
input a new expression:
bye
program exits
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/149515.html Link to the original text :https://javaforall.cn
边栏推荐
- Notion 类笔记软件如何选择?Notion 、FlowUs 、Wolai 对比评测
- Idea设置方法注释和类注释
- 【MySQL 使用秘籍】一網打盡 MySQL 時間和日期類型與相關操作函數(三)
- Shandong University Summer Training - 20220620
- leetcode 10. Regular Expression Matching 正则表达式匹配 (困难)
- stm32逆向入门
- mysql econnreset_ Nodejs socket error handling error: read econnreset
- FPGA learning notes: vivado 2019.1 add IP MicroBlaze
- JPA规范总结和整理
- MSTP and eth trunk
猜你喜欢
Sorry, we can't open xxxxx Docx, because there is a problem with the content (repackaging problem)
C# 对象存储
Flutter draws animation effects of wave movement, curves and line graphs
MMSeg——Mutli-view时序数据检查与可视化
MySQL - database query - sort query, paging query
Principle and configuration of RSTP protocol
CAN和CAN FD
[daily question] 1200 Minimum absolute difference
What happened to the communication industry in the first half of this year?
RHCSA8
随机推荐
Matlab paper chart standard format output (dry goods)
mysql econnreset_ Nodejs socket error handling error: read econnreset
Reverse Polish notation
真正的缓存之王,Google Guava 只是弟弟
法国学者:最优传输理论下对抗攻击可解释性探讨
4年工作经验,多线程间的5种通信方式都说不出来,你敢信?
面试官灵魂拷问:为什么代码规范要求 SQL 语句不要过多的 join?
爱可生SQLe审核工具顺利完成信通院‘SQL质量管理平台分级能力’评测
Realize the addition of all numbers between 1 and number
Win10 - lightweight gadget
Huawei push service content, read notes
Simple page request and parsing cases
【服务器数据恢复】某品牌服务器存储raid5数据恢复案例
Mmseg - Mutli view time series data inspection and visualization
Flutter InkWell & Ink组件
TortoiseSVN使用情形、安装与使用
Cloudcompare - point cloud slice
Nantong online communication group
【Hot100】34. 在排序数组中查找元素的第一个和最后一个位置
Could not set property ‘id‘ of ‘class XX‘ with value ‘XX‘ argument type mismatch 解决办法