Catalog
Josephu (Joseph, Joseph Ring) Problem
An Idea for Constructing a One-way Ring Chain List
Illustration and implementation of Joseph problem analysis (1)
Illustration and implementation of Joseph problem analysis (2)
Scenarios and introduction of stacks
Application scenarios for stacks
Thought analysis diagram of array simulation stack
Stack implementation synthesizer
Prefix, infix, suffix expression
Prefix expression (Polish expression)
Computer evaluation of suffix expressions
Analysis and Implementation of Inverse Polish Calculator
Analysis of Ideas of Interfix to Suffix
One-way Ring Chain List
Josephu (Joseph, Joseph Ring) Problem
Josephu's question is: Set the number 1,2,... N for n people to sit in a circle, and specify that the person numbered K (1<=k<=n) will count from the beginning, the person counting to m will be listed, the next person counting from the beginning, the person counting to m will be listed again, and so on, until everyone counts, resulting in a sequence of column numbers.
Tips
To solve the Josephu problem, a circular chain list with n nodes is constructed, and then counted from k nodes to M. When m is remembered, the corresponding nodes are deleted from the chain list, and then counted from the next node of the deleted node to the next node, until the last node is deleted from the chain table and the algorithm ends.
Sketch Map
n=5, that is, 5 people
k=1, counting from the first person - - > one-way ring list complete, Joseph problem
m=2, number 2
An Idea for Constructing a One-way Ring Chain List
1. Create the first node first so that first points to it and forms a ring
2. Later, when we create a new node, we add it to the existing ring list.
Traversing Ring Chain List
1. Let an auxiliary pointer (variable) curBoy point to the first node first
2. Then curBoy.next==first ends by traversing the ring list through a while loop
Illustration and implementation of Joseph problem analysis (1)
Complete Code
package linkedlist;
public class Josepfu {
public static void main(String[] args) {
//Test one to see if the ring list and traversal are ok
CircleSingleLinkedList circleSingleLinkedList=new CircleSingleLinkedList();
circleSingleLinkedList.addBoy(5);//Join 5 child nodes
circleSingleLinkedList.showBoy();
}
}
//Create a one-way chain table with a ring shape
class CircleSingleLinkedList{
//Create a first node with no current number
private Boy first=null;
//Add child nodes to build a ring-shaped chain table
public void addBoy(int nums) {
//nums does a data check
if (nums<1) {
System.out.println("nums Incorrect value for");
return;
}
Boy curBoy=null;//Auxiliary pointer to help build a ring list
//Use for to create our ring list
for (int i = 0; i <=nums; i++) {
//Create a child node by number
Boy boy=new Boy(i);
//If it's the first child
if (i==1) {
first=boy;
first.setNext(first);//Composition Ring
curBoy=first;//Point curBoy at the first child
}else {
curBoy.setNext(boy);
boy.setNext(first);
curBoy=boy;
}
}
}
//Traverse through the current ring list
public void showBoy() {
//Determine if the list is empty
if (first==null) {
System.out.println("No children~~");
return;
}
//Because first cannot move, we still use a secondary pointer to complete the traversal
Boy curBoy=first;
while (true) {
System.out.printf("Number of child%d\n",curBoy.getNo());
if (curBoy.getNext()==first) {//Description has been traversed
break;
}
curBoy=curBoy.getNext();//curBoy Move Back
}
}
}
//Create a Boy class representing a node
class Boy{
private int no;//number
private Boy next;//Point to next node, default null
public Boy(int no) {
this.no=no;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public Boy getNext() {
return next;
}
public void setNext(Boy next) {
this.next = next;
}
}Illustration and implementation of Joseph problem analysis (2)
Generate the order in which a child leaves the circle based on user input
1. You need to create an auxiliary pointer (variable) helper that should point to the last node of the ring list beforehand
Supplement: Let first and helper move k-1 times before children report
2. Let the first and helper pointers move m-1 times at the same time before the child counts
3. You can then circle the child node that first points to
first=first.next;
helper.next=first
Node originally pointed to by first has no reference and is recycled
The order of ringing: 2->4->1->5->3
//Calculate the order in which children go out of circles based on user input
/*
* startNo Indicates the number from which child to begin
* countNum Represent Count
* nums Indicates how many children were in the circle initially
* */
public void countBoy(int startNo,int countNum,int nums) {
//Validate data first
if (first==null||startNo<1||startNo>nums) {
System.out.println("Error in parameter input, please re-enter");
return;
}
//Create an auxiliary pointer to help your child out of the circle
Boy helper=first;
//You need to create a pointer variable helper that should point to the last node of the ring list
while (true) {
if (helper.getNext()==first) {//Explain that helper points to the last child node
break;
}
helper=helper.getNext();
}
//Let first and helper move k-1 times before your child counts
for (int j = 0; j < startNo-1; j++) {
first=first.getNext();
helper=helper.getNext();
}
//When a child counts, let the first and helper pointers move k-1 times at the same time, then go out of the circle
//This is a looping operation, knowing that there is only one node in the loop
while (true) {
if (helper==first) {//There is only one node in the circle
break;
}
//Let the first and helper pointers move countNum-1 at the same time, then go out of circle
for (int j = 0; j <countNum; j++) {
first=first.getNext();
helper=helper.getNext();
}
//The first node is the child node to circle
System.out.printf("Child%d Out of Circle\n",first.getNo());
//Circle the child node that first points to
first=first.getNext();
helper.setNext(first);
}
System.out.printf("Last child number left in circle%d\n",helper.getNo());
}Complete Code
package linkedlist;
public class Josepfu {
public static void main(String[] args) {
//Test one to see if the ring list and traversal are ok
CircleSingleLinkedList circleSingleLinkedList=new CircleSingleLinkedList();
circleSingleLinkedList.addBoy(5);//Join 5 child nodes
circleSingleLinkedList.showBoy();
//Test if a child is out of circle correctly
circleSingleLinkedList.countBoy(10, 20, 125);
}
}
//Create a one-way chain table with a ring shape
class CircleSingleLinkedList{
//Create a first node with no current number
private Boy first=null;
//Add child nodes to build a ring-shaped chain table
public void addBoy(int nums) {
//nums does a data check
if (nums<1) {
System.out.println("nums Incorrect value for");
return;
}
Boy curBoy=null;//Auxiliary pointer to help build a ring list
//Use for to create our ring list
for (int i = 0; i <=nums; i++) {
//Create a child node by number
Boy boy=new Boy(i);
//If it's the first child
if (i==1) {
first=boy;
first.setNext(first);//Composition Ring
curBoy=first;//Point curBoy at the first child
}else {
curBoy.setNext(boy);
boy.setNext(first);
curBoy=boy;
}
}
}
//Traverse through the current ring list
public void showBoy() {
//Determine if the list is empty
if (first==null) {
System.out.println("No children~~");
return;
}
//Because first cannot move, we still use a secondary pointer to complete the traversal
Boy curBoy=first;
while (true) {
System.out.printf("Number of child%d\n",curBoy.getNo());
if (curBoy.getNext()==first) {//Description has been traversed
break;
}
curBoy=curBoy.getNext();//curBoy Move Back
}
}
//Calculate the order in which children go out of circles based on user input
/*
* startNo Indicates the number from which child to begin
* countNum Represent Count
* nums Indicates how many children were in the circle initially
* */
public void countBoy(int startNo,int countNum,int nums) {
//Validate data first
if (first==null||startNo<1||startNo>nums) {
System.out.println("Error in parameter input, please re-enter");
return;
}
//Create an auxiliary pointer to help your child out of the circle
Boy helper=first;
//You need to create a pointer variable helper that should point to the last node of the ring list
while (true) {
if (helper.getNext()==first) {//Explain that helper points to the last child node
break;
}
helper=helper.getNext();
}
//Let first and helper move k-1 times before your child counts
for (int j = 0; j < startNo-1; j++) {
first=first.getNext();
helper=helper.getNext();
}
//When a child counts, let the first and helper pointers move k-1 times at the same time, then go out of the circle
//This is a looping operation, knowing that there is only one node in the loop
while (true) {
if (helper==first) {//There is only one node in the circle
break;
}
//Let the first and helper pointers move countNum-1 at the same time, then go out of circle
for (int j = 0; j <countNum; j++) {
first=first.getNext();
helper=helper.getNext();
}
//The first node is the child node to circle
System.out.printf("Child%d Out of Circle\n",first.getNo());
//Circle the child node that first points to
first=first.getNext();
helper.setNext(first);
}
System.out.printf("Last child number left in circle%d\n",helper.getNo());
}
}
//Create a Boy class representing a node
class Boy{
private int no;//number
private Boy next;//Point to next node, default null
public Boy(int no) {
this.no=no;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public Boy getNext() {
return next;
}
public void setNext(Boy next) {
this.next = next;
}
}Scenarios and introduction of stacks
Introduction to Stack
1) The English of the stack is stack
2) The stack is an ordered list of first in, then out
3) A stack is a special linear table that restricts the insertion and deletion of elements in a linear table to occur only at the same end of the linear table. One end that allows insertion and deletion is called the top of the stack and the other end is the fixed end, called the bottom of the stack.
4) According to the definition of stack, the elements first placed in the stack are at the bottom of the stack, the elements last placed are at the top of the stack, while deleting elements is just the opposite. The elements last placed are deleted first, the elements first placed are deleted last.
The concepts of pop and push
Application scenarios for stacks
1) Call of a subprogram: Before jumping to a subprogram, the address of the next instruction will be stored on the stack until the subprogram is executed before taking out the address to return to the original program.
2) Processing recursive calls: Similar to the call of a subroutine, except that in addition to the address where the next instruction is stored, data such as parameters, region variables, and so on are stored on the stack.
3) Conversion of expression [suffix expression to suffix expression] and evaluation (actual solution)
4) Traversal of Binary Trees
5) depth-first search method for graphics
Thought analysis diagram of array simulation stack
Ideas for implementing stacks
1. Use arrays to simulate stacks
2. Define a top to represent the top of the stack, initialized to -1
3. Operation on the stack, when data is added to the stack, top++;stack[top]=data
4. Out-of-stack operation, int value=stack[top];top--;return value
Complete Code
package stack;
import java.util.Scanner;
public class ArrayStackDemo {
public static void main(String[] args) {
//Test if ArrayStack is correct
//First create an ArrayStack object - > Representation Stack
ArrayStack stack=new ArrayStack(4);
String key="";
boolean loop=true;//Controls whether to exit the menu
Scanner scanner=new Scanner(System.in);
while (loop) {
System.out.println("show:Represents a display stack");
System.out.println("exit:Exit the program");
System.out.println("push:Represents adding data to the stack(Push)");
System.out.println("pop:Represents taking data out of the stack(Stack Out)");
System.out.println("Please enter your choice");
key=scanner.next();
switch (key) {
case "show":
stack.list();
break;
case "push":
System.out.println("Please enter a number");
int value=scanner.nextInt();
stack.push(value);
break;
case "pop":
try {
int res=stack.pop();
System.out.printf("The stacked data is%d",res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case "exit":
scanner.close();
loop=false;
break;
default:
break;
}
}
System.out.println("Program Exit~~");
}
}
//Define an ArrayStack Representation Stack
class ArrayStack{
private int maxSize;//Stack size
private int[] stack;//Array, array simulation stack, where the data is placed
private int top=-1;//Top represents the top of the stack, initialized to -1
//constructor
public ArrayStack(int maxSize) {
this.maxSize=maxSize;
stack=new int[this.maxSize];
}
//Full stack
public boolean isFull() {
return top==maxSize-1;
}
//Stack empty
public boolean isEmpty() {
return top==-1;
}
//Push
public void push(int value) {
//First judge if it is full
if (isFull()) {
System.out.println("Full stack");
return;
}
top++;
stack[top]=value;
}
//Out-pop, return data from the top of the stack
public int pop() {
//First determine if the stack is empty
if (isEmpty()) {
//throw
throw new RuntimeException("Stack empty, no data");
}
int value=stack[top];
top--;
return value;
}
//Show the stack [traverse the stack], when traversing, you need to display data from the top of the stack
public void list() {
if (isEmpty()) {
System.out.println("Stack empty, no data~~");
return;
}
//Data needs to be displayed from the top of the stack
for (int i = top; i>=0; i--) {
System.out.printf("stack[%d]=%d\n",i,stack[i]);
}
}
}Run Results
Stack implementation synthesizer
Idea Analysis (1)
The idea of using stack to complete expression calculation
1. Traverse through our expression with an index value
2. If we find a number, we go directly to the stack
3. If you find that the scan is a symbol, the following are true
3.1 If the current symbol stack is found to be empty, go directly to the stack
3.2 If the symbol stack has operators, compare. If the priority of the current operator is less than or equal to the operator in the stack, you need to pop out two numbers from the stack, pop out a symbol from the symbol stack, perform the operation, and you will get the result, put the current operator on the symbol stack, and then put the current operator on the symbol stack if the priority of the current operator is greater than the operation in the stack.Character, directly into the symbol stack.
4. When the expression is scanned, pop out the corresponding numbers and symbols from the stack of numbers and symbols sequentially and run.
5. The last number on the stack is the result of the expression.
Verification: 3+2*6-2=13
Code implementation (2)
Complete Code
package stack;
public class Calculator {
public static void main(String[] args) {
//Complete the expression according to the previous teacher's ideas
String expression="3+2*6-2";
//Create two stacks, a number stack, a symbol stack
ArrayStack2 numStack=new ArrayStack2(10);
ArrayStack2 operStack=new ArrayStack2(10);
//Define the required related variables
int index=0;//For Scanning
int num1=0;
int num2=0;
int oper=0;
int res=0;
char ch=' ';//Save char from each scan to ch
//Start the scan expression for the while loop
while(true) {
//Get each character of expression in turn
ch=expression.substring(index,index+1).charAt(0);
//Determine what ch is, and then do the appropriate processing
if (operStack.isoper(ch)) {//If it is an operator
//Determine if the current symbol stack is empty
if (!operStack.isEmpty()) {
//If the symbol stack has operators, compare if the priority of the current operator is less than or equal to the operator in the stack.
//You need to pop out two numbers from the stack and a symbol from the stack.
//The result is put on the stack of numbers, then the current operator is put on the stack of symbols.
//If the priority of the current operator is greater than that of the operator in the stack, it goes directly to the symbol stack.
if (operStack.priority(ch)<=operStack.priority(operStack.peek())) {
num1=numStack.pop();
num2=numStack.pop();
oper=operStack.pop();
res=numStack.cal(num1, num2, oper);
//The result of an operation is like a stack of numbers
numStack.push(res);
//Then put the current operator on the symbol stack
operStack.push(ch);
}else {
//If the priority of the current operator is greater than that of the operator in the stack, it goes directly to the symbol stack
operStack.push(ch);
}
}else {
//If empty directly into the symbol line
operStack.push(ch);
}
}else {//If it is a number, go directly to the number stack
numStack.push(ch-48);
}
//Let index+1, and determine whether to scan to the end of expression
index++;
if (index>=expression.length()) {
break;
}
}
//When the expression is scanned, the corresponding numbers and symbols are pop ped out of the stack of numbers and symbols sequentially and run.
while (true) {
//If the symbol stack is empty, the final result is calculated, with only one number in the stack [result]
if (operStack.isEmpty()) {
break;
}
num1=numStack.pop();
num2=numStack.pop();
oper=operStack.pop();
res=numStack.cal(num1, num2, oper);
numStack.push(res);
}
//pop out the last number of stacks as a result
int res2=numStack.pop();
System.out.printf("Expression%s=%d",expression,res2);
}
}
//Create a stack first, using the previous one directly
//Define an ArrayStack2 Representation Stack
class ArrayStack2{
private int maxSize;//Stack size
private int[] stack;//Array, array simulation stack, where the data is placed
private int top=-1;//Top represents the top of the stack, initialized to -1
//constructor
public ArrayStack2(int maxSize) {
this.maxSize=maxSize;
stack=new int[this.maxSize];
}
//Add a method. You can return the value at the top of the current stack, but it's not a real pop
public int peek() {
return stack[top];
}
//Full stack
public boolean isFull() {
return top==maxSize-1;
}
//Stack empty
public boolean isEmpty() {
return top==-1;
}
//Push
public void push(int value) {
//First judge if it is full
if (isFull()) {
System.out.println("Full stack");
return;
}
top++;
stack[top]=value;
}
//Out-pop, return data from the top of the stack
public int pop() {
//First determine if the stack is empty
if (isEmpty()) {
//throw
throw new RuntimeException("Stack empty, no data");
}
int value=stack[top];
top--;
return value;
}
//Show the stack [traverse the stack], when traversing, you need to display data from the top of the stack
public void list() {
if (isEmpty()) {
System.out.println("Stack empty, no data~~");
return;
}
//Data needs to be displayed from the top of the stack
for (int i = top; i>=0; i--) {
System.out.printf("stack[%d]=%d\n",i,stack[i]);
}
}
//Returns the priority of the operator, which is determined by the programmer, and is represented by a number
//The larger the number, the higher the priority
public int priority(int oper) {
if (oper=='*'||oper=='/') {
return 1;
}else if (oper=='*'||oper=='-') {
return 0;
}else {
return -1;//Assume that the current expression is only +, -, *, /
}
}
//Determine if it is an operator
public boolean isoper(char val) {
return val=='+'||val=='-'||val=='*'||val=='/';
}
//computing method
public int cal(int num1,int num2,int oper) {
int res=0;//res is used to store the results of the calculation
switch(oper) {
case'+':
res=num1+num2;
break;
case'-':
res=num2-num1;
break;
case'*':
res=num1*num2;
break;
case'/':
res=num1/num2;
break;
default:
break;
}
return res;
}
}Run Results
Code implementation (3)
String keepNum=" ";//For splicing multiple digits
//numStack.push(ch-48);
//Analysis ideas
//1. When dealing with multidigits, one cannot be found and immediately stacked, because it may be multidigits
//2. In the case of numbers, you need to look at one bit after index of the expression, scan for numbers, and stack for symbols
//3. So we need to define a variable string for splicing
//Processing multi-digit
keepNum+=ch;
//If ch is already the last expression, go directly to the stack
if (index==expression.length()-1) {
numStack.push(Integer.parseInt(keepNum));
}else {
//Determines whether the next character is a number, continues scanning if it is a number, and stacks if it is an operator
//Note that the latter one, not index++,
if (operStack.isoper(expression.substring(index+1,index+2).charAt(0))) {
//If the latter bit is an operator, keep Num="1" or "123" on the stack
numStack.push(Integer.parseInt(keepNum));
//Important!!!,Keep Num empty
keepNum=" ";
}
}Complete Code
package stack;
public class Calculator {
public static void main(String[] args) {
//Complete the expression according to the previous teacher's ideas
String expression="7*2*2-5+1-5+3-4";
//Create two stacks, a number stack, a symbol stack
ArrayStack2 numStack=new ArrayStack2(10);
ArrayStack2 operStack=new ArrayStack2(10);
//Define the required related variables
int index=0;//For Scanning
int num1=0;
int num2=0;
int oper=0;
int res=0;
char ch=' ';//Save char from each scan to ch
String keepNum=" ";//For splicing multiple digits
//Start the scan expression for the while loop
while(true) {
//Get each character of expression in turn
ch=expression.substring(index,index+1).charAt(0);
//Determine what ch is, and then do the appropriate processing
if (operStack.isoper(ch)) {//If it is an operator
//Determine if the current symbol stack is empty
if (!operStack.isEmpty()) {
//If the symbol stack has operators, compare if the priority of the current operator is less than or equal to the operator in the stack.
//You need to pop out two numbers from the stack and a symbol from the stack.
//The result is put on the stack of numbers, then the current operator is put on the stack of symbols.
//If the priority of the current operator is greater than that of the operator in the stack, it goes directly to the symbol stack.
if (operStack.priority(ch)<=operStack.priority(operStack.peek())) {
num1=numStack.pop();
num2=numStack.pop();
oper=operStack.pop();
res=numStack.cal(num1, num2, oper);
//The result of an operation is like a stack of numbers
numStack.push(res);
//Then put the current operator on the symbol stack
operStack.push(ch);
}else {
//If the priority of the current operator is greater than that of the operator in the stack, it goes directly to the symbol stack
operStack.push(ch);
}
}else {
//If empty directly into the symbol line
operStack.push(ch);
}
}else {//If it is a number, go directly to the number stack
//numStack.push(ch-48);
//Analysis ideas
//1. When dealing with multidigits, one cannot be found and immediately stacked, because it may be multidigits
//2. In the case of numbers, you need to look at one bit after index of the expression, scan for numbers, and stack for symbols
//3. So we need to define a variable string for splicing
//Processing multi-digit
keepNum+=ch;
//If ch is already the last expression, go directly to the stack
if (index==expression.length()-1) {
numStack.push(Integer.parseInt(keepNum));
}else {
//Determines whether the next character is a number, continues scanning if it is a number, and stacks if it is an operator
//Note that the latter one, not index++,
if (operStack.isoper(expression.substring(index+1,index+2).charAt(0))) {
//If the latter bit is an operator, keep Num="1" or "123" on the stack
numStack.push(Integer.parseInt(keepNum));
//Important!!!,Keep Num empty
keepNum=" ";
}
}
}
//Let index+1, and determine whether to scan to the end of expression
index++;
if (index>=expression.length()) {
break;
}
}
//When the expression is scanned, the corresponding numbers and symbols are pop ped out of the stack of numbers and symbols sequentially and run.
while (true) {
//If the symbol stack is empty, the final result is calculated, with only one number in the stack [result]
if (operStack.isEmpty()) {
break;
}
num1=numStack.pop();
num2=numStack.pop();
oper=operStack.pop();
res=numStack.cal(num1, num2, oper);
numStack.push(res);
}
//pop out the last number of stacks as a result
int res2=numStack.pop();
System.out.printf("Expression%s=%d",expression,res2);
}
}
//Create a stack first, using the previous one directly
//Define an ArrayStack2 Representation Stack
class ArrayStack2{
private int maxSize;//Stack size
private int[] stack;//Array, array simulation stack, where the data is placed
private int top=-1;//Top represents the top of the stack, initialized to -1
//constructor
public ArrayStack2(int maxSize) {
this.maxSize=maxSize;
stack=new int[this.maxSize];
}
//Add a method. You can return the value at the top of the current stack, but it's not a real pop
public int peek() {
return stack[top];
}
//Full stack
public boolean isFull() {
return top==maxSize-1;
}
//Stack empty
public boolean isEmpty() {
return top==-1;
}
//Push
public void push(int value) {
//First judge if it is full
if (isFull()) {
System.out.println("Full stack");
return;
}
top++;
stack[top]=value;
}
//Out-pop, return data from the top of the stack
public int pop() {
//First determine if the stack is empty
if (isEmpty()) {
//throw
throw new RuntimeException("Stack empty, no data");
}
int value=stack[top];
top--;
return value;
}
//Show the stack [traverse the stack], when traversing, you need to display data from the top of the stack
public void list() {
if (isEmpty()) {
System.out.println("Stack empty, no data~~");
return;
}
//Data needs to be displayed from the top of the stack
for (int i = top; i>=0; i--) {
System.out.printf("stack[%d]=%d\n",i,stack[i]);
}
}
//Returns the priority of the operator, which is determined by the programmer, and is represented by a number
//The larger the number, the higher the priority
public int priority(int oper) {
if (oper=='*'||oper=='/') {
return 1;
}else if (oper=='*'||oper=='-') {
return 0;
}else {
return -1;//Assume that the current expression is only +, -, *, /
}
}
//Determine if it is an operator
public boolean isoper(char val) {
return val=='+'||val=='-'||val=='*'||val=='/';
}
//computing method
public int cal(int num1,int num2,int oper) {
int res=0;//res is used to store the results of the calculation
switch(oper) {
case'+':
res=num1+num2;
break;
case'-':
res=num2-num1;
break;
case'*':
res=num1*num2;
break;
case'/':
res=num1/num2;
break;
default:
break;
}
return res;
}
}Prefix, infix, suffix expression
Prefix expression (Polish expression)
Scan the expression from right to left, push the number into the stack when it encounters a number, pop up the two numbers at the top of the stack when it encounters an operator, calculate them accordingly with the operator (top and second top elements of the stack), and stack the results: Repeat the above process to know the leftmost end of the expression, and the last calculated value is the result of the expression.
Infix expression
1) Infix expressions are common operations, such as (3+4)*5-6
2) The evaluation of a suffix expression is the most familiar to us, but it is not easy to operate on a computer (as we have seen in the previous case), so when calculating the result, we often convert the suffix expression into another expression to operate on (usually into a suffix expression).
Postfix Expression
1) A suffix expression, also known as an inverse Polish expression, is similar to a prefix expression except that the operator follows the operator
2) Examples are given as follows: (3+4)*5-6 corresponds to a suffix expression of 34+5*6-
Computer evaluation of suffix expressions
Scan the expression from left to right, push the number into the stack when it encounters a number, pop up two numbers at the top of the stack when it encounters an operator, calculate them accordingly with the operator (the next top element and the top element of the stack), and stack the results: repeat the process until the rightmost end of the expression, and the result of the operation is the result of the expression.
Analysis and Implementation of Inverse Polish Calculator
Complete Code
package stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class PolandNotation {
public static void main(String[] args) {
//Define first to the inverse Polish expression
//(3+4)*5-6=>3 4+5*6-
//Explain that for convenience, the numbers and symbols of the inverse Polish expression are separated by spaces
String suffixExpression="3 4+5*6-";
//thinking
//1. Put "3 4+5*6-"=>in ArrayList first
//2. Pass the ArrayList to a method that traverses the ArrayList with the stack to complete the calculation
List<String> list=getListString(suffixExpression);
System.out.println("rpnList"+list);
int res=calculate(list);
System.out.println("The result of the calculation is="+res);
}
//Put an inverse Polish expression, data and operators into the ArrayList in turn
public static List<String>getListString(String suffixExpression){
//Split suffixExpression
String[] split=suffixExpression.split("");
List<String> list=new ArrayList<String>();
for (String ele:split) {
list.add(ele);
}
return list;
}
//Complete the operation of the inverse Polish expression
public static int calculate(List<String>ls) {
//Create to a stack, just one stack is required
Stack<String> stack=new Stack<String>();
//Traversing ls
for (String item:ls) {
//Use regular expressions to take out numbers here
if (item.matches("\\d+")) {//Multiple digits matched
//Push
stack.push(item);
}else {
//pop out two numbers, combine them, and put them on the stack
int num2=Integer.parseInt(stack.pop());
int num1=Integer.parseInt(stack.pop());
int res=0;
if (item.equals("+")) {
res=num1+num2;
}else if (item.equals("-")) {
res=num1-num2;
}else if (item.equals("*")) {
res=num1*num2;
}else if (item.equals("/")) {
res=num1/num2;
}else {
throw new RuntimeException("Error in operation");
}
//Put res on the stack
stack.push(""+res);
}
}
//The last data left in the stack is the result of the operation
return Integer.parseInt(stack.pop());
}
}Analysis of Ideas of Interfix to Suffix
Ideas and Steps Analysis
Code implementation
package stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class PolandNotation {
public static void main(String[] args) {
//Complete converting a suffix expression to a suffix expression to get functionality
//Explain
//1.1+((2+3)*4) -5=> to 1 2 3+4*+5-
//2.Because it is inconvenient to operate str directly, first List the expression "1+((2+3)*4) -5"=>infix
//That is,'1+((2+3)*4) -5'=>ArrayList [1,+, (, (, 2,+, 3,), *, 4,)-, 5]
//3. List=>List corresponding to the suffix expression that you get
String expression="1+((2+3)*4)-5";
List<String>infixExpressionList=toInfixExpressionList(expression);
System.out.println("Corresponding to infix expression List"+infixExpressionList);
List<String> suffixExpressionList=parseSuffixExpressionList(infixExpressionList);
System.out.println("Corresponding to the suffix expression List"+suffixExpressionList);
System.out.printf("expression",calculate(suffixExpressionList));
//Define first to the inverse Polish expression
//(3+4)*5-6=>3 4+5*6-
//Explain that for convenience, the numbers and symbols of the inverse Polish expression are separated by spaces
String suffixExpression="30 4+5*6-";
//thinking
//1. Put "3 4+5*6-"=>in ArrayList first
//2. Pass the ArrayList to a method that traverses the ArrayList with the stack to complete the calculation
List<String> list=getListString(suffixExpression);
System.out.println("rpnList"+list);
int res=calculate(list);
System.out.println("The result of the calculation is="+res);
}
//That is, ArrayList [1, +, (, 2, +, 3,), *, 4,), -, 5]=>ArrayList [1, 2, 3, 4, *, +, 5,-]
//Method: Convert the infix expression to the corresponding List
public static List<String>parseSuffixExpressionList(List<String> ls){
//Define two stacks
Stack<String> s1=new Stack<String>();//Symbol stack
//Note: Because s2 is a stack, there is no pop operation during the whole conversion process, and we need to output in reverse order later
//So it's cumbersome, so we don't need Stack<String>to use List<String>s2 directly here
//Stack<String> s2=new Stack<String>();//Stack S2 storing intermediate results
List<String>s2=new ArrayList<String>();//List s2 storing intermediate results
//Traversing ls
for (String item:ls) {
//If it's a number, add s2
if (item.matches("\\d+")) {
s2.add(item);
}else if (item.equals("(")) {
s1.push(item);
}else if (item.equals("")) {
//If it is the right parenthesis')', pop up the operator at the top of the s1 stack and press s2 until
//When left parentheses are encountered, discard them
while (!s1.peek().equals("(")) {
s2.add(s1.pop());
}
s1.pop();//!!!Will (pop up s1 stack, remove parentheses
}else {
//When the item's priority is less than or equal to the s1 stack top operator,
//Pop up the operator at the top of the s1 stack, add it to s2, go to (4.1) again, and compare it with the top operator in s1
//Question: We really don't have a way to compare priorities
while (s1.size()!=0&&Operation.getValue(s1.peek())>=Operation.getValue(item)){
s2.add(s1.pop());
}
//You also need to push item s onto the stack
s1.push(item);
}
}
//Pop up the remaining operators in s1 and add s2
while (s1.size()!=0) {
s2.add(s1.pop());
}
return s2;//Note that since it is stored in a List, the sequential output is the corresponding suffix expression
}
public static List<String> toInfixExpressionList(String s){
//Define a List to hold the contents of the infix expression
List<String> ls=new ArrayList<String>();
int i=0;//This is a pointer that traverses the infix expression string
String str;//Stitching of multiple digits
char c;//For each character traversed, place it in c
do {
//If c is a non-number, I need to join ls
if ((c=s.charAt(i))<48||(c=s.charAt(i))>57) {
ls.add(""+c);
i++;//i Need to move back
}else {//If it is a number, consider multiple digits
str="";//Set str to ""
while (i<s.length()&&(c=s.charAt(i))>=48&&(c=s.charAt(i))<=57) {
str+=c;//Stitching
i++;
}
ls.add(str);
}
}while(i<s.length());
return ls;//Return
}
//Put an inverse Polish expression, data and operators into the ArrayList in turn
public static List<String>getListString(String suffixExpression){
//Split suffixExpression
String[] split=suffixExpression.split("");
List<String> list=new ArrayList<String>();
for (String ele:split) {
list.add(ele);
}
return list;
}
//Complete the operation of the inverse Polish expression
public static int calculate(List<String>ls) {
//Create to a stack, just one stack is required
Stack<String> stack=new Stack<String>();
//Traversing ls
for (String item:ls) {
//Use regular expressions to take out numbers here
if (item.matches("\\d+")) {//Multiple digits matched
//Push
stack.push(item);
}else {
//pop out two numbers, combine them, and put them on the stack
int num2=Integer.parseInt(stack.pop());
int num1=Integer.parseInt(stack.pop());
int res=0;
if (item.equals("+")) {
res=num1+num2;
}else if (item.equals("-")) {
res=num1-num2;
}else if (item.equals("*")) {
res=num1*num2;
}else if (item.equals("/")) {
res=num1/num2;
}else {
throw new RuntimeException("Error in operation");
}
//Put res on the stack
stack.push(""+res);
}
}
//The last data left in the stack is the result of the operation
return Integer.parseInt(stack.pop());
}
}
//Writing an Operation-like class returns the priority corresponding to an operator
class Operation{
private static int ADD=1;
private static int SUB=1;
private static int MUL=2;
private static int DIV=2;
//Write a method that returns the corresponding priority number
public static int getValue(String operation) {
int result=0;
switch(operation) {
case"+":
result=ADD;
break;
case "-":
result=SUB;
break;
case "*":
result=MUL;
break;
case "/":
result=DIV;
break;
default:
System.out.println("The operation does not exist");
}
return result;
}
}