This is the 20th day of my participation in the Gwen Challenge.[More Challenges]
Hello ah, I am gray little ape, a super will write bug program ape!
Welcome to pay attention to my column “daily Blue bridge”, the main role of this column is to share with you in recent years blue Bridge Cup provincial competition and the final and other real questions, analysis of the existing algorithm ideas, data structure and other content, to help you learn more knowledge and technology!
Title: Inverse Polish expressions
The normal expression is called infix expression, the operator in the middle, is mainly for people to read, machine solution is not convenient
For example, 3 + 5 x (2 + 6) -1
And it’s often necessary to use parentheses to list the order of operations,
Conversely, if the inverse Polish expression (prefix expression) is used, the above expression would be:
Minus 3 times 5 plus 2, 6, 1
Without parentheses, the machine can solve the problem recursively
For simplicity, let’s assume:
1. There are only three + – * operators
2. Each operand is a non-negative integer less than 10
The following program evaluates an inverse Polish representation string,
The return value is a piece of data, where the first element represents the result of the evaluation and the second element represents the number of characters it has parsed
static int [] evaluste(String x) {
if (x.length()==0) {
Return new int [] {0, 0};
}
char c = x.charAt(0);
if (c>=’0’&&c<=’9′) {
return new int[] {c-‘0’,1};
}
int[] v1 = evaluste(x.substring(1));
int[] v2 = _________________________________; // Fill in the blanks
int v = Integer.MAX_VALUE;
if(c==’+’) v = v1[0] + v2[0];
if(c==’*’) v = v1[0] * v2[0];
if(c==’-‘) v = v1[0] – v2[0];
return new int[] {v,1 + v1[1] + v2[1]};
}
Please analyze the code logic and guess the code at the underline, submit through the web page
Note: only use the missing code as your answer. do not fill in extra code, symbols or captions!!
Answer:
The key to solve the problem is to read through the source code, understand the specific functions of each line to achieve, and then understand the main ideas of the program design, according to the requirements of the blank can be completed,
A detailed explanation of the source code can be found in the answers below.
Answer source:
Package 2013 Provincial competition Public class Year2013_t6 {public static void main(String[] args) { 3+5*(2+6)-1=42 int a[] = evaluste("-+3*5+261"); System.out.println(a[0]); Evaluste (String x) {evaluste(String x) {evaluste(String x) {evaluste(String x) {evaluste(String x) {evaluste(String x); If (x.length()==0) {return new int[] {0,0}; } char c = x.charAt(0); / / get the first character of a string if > = '0' (c & c < = '9') {/ / figure out whether the character number return new int [] {c - '0', 1}; Evaluste (x.substring(1)); evaluste(x.substring(1)); Int [] v2 = evaluste(x.substring(1+v1[1])); Int v = integer.max_value; int v = integer.max_value; // According to the type of the first character. If (c=='+') v = v1[0] + v2[0]; if(c=='*') v = v1[0] * v2[0]; if(c=='-') v = v1[0] - v2[0]; return new int[] {v,1 + v1[1] + v2[1]}; // Return the processing result}}Copy the code
Example output:
There are deficiencies or improvements, but also hope that small partners put forward messages, learn together!
Interested partners can pay attention to the column!
Grey ape accompany you to progress together!
Finally, I am participating in the contest for 2020 Blogger of the Year. Please help me vote for it!
Vote link:Bss.csdn.net/m/topic/blo…
