The data structure of this stack is a little longer but not difficult, so you can understand it with a little heart. The code has been optimized and tested to account for as many predictable errors as possible.
This is the 11th day of my participation in Gwen Challenge
A practical requirement for the stack
Calculation formula: [722-5+1-5+3-3]
Excuse me: the bottom of the computer is how to calculate the results? Note that it is not simply a list of operations, because we can see this directly, but how does a computer understand this operation (to a computer, it receives a string), and that is what we are talking about -> stack
Introduction to the stack (important)
Stack is a filo-first In Last Out (filo-first In Last Out) ordered list.
A stack is a special kind of linear table that limits the insertion and deletion of elements to the same end of the linear table. The changing end of the stack is called the Top, and the fixed end is called the Bottom.
According to the definition of the stack, the first element to be added to the stack is at the bottom of the stack, and the last element to be added is at the top of the stack.
Stack application scenarios
1) Call of subroutine: before jumping to the subroutine, the address of the next instruction will be stored on the stack until the subroutine is executed, and then the address will be removed to return to the original program.
2) Recursive call processing: similar to subroutine call, except that in addition to storing the address of the next instruction, parameters, area variables and other data into the stack.
3) expression conversion [infix expression to suffix expression] and evaluation (actual solution).
4) Binary tree traversal.
5) Depth first search method of graph.
Array emulation stack
Because the stack is an ordered list, of course, you can use the structure of the array to store the data content of the stack, we will use the array to simulate the stack out of the stack, into the stack and other operations.
Key point: You need onetopVariable to represent the top of the stack, initialized to -1 to indicate that the stack is empty.
The stack is very simple, top++ on the stack, top– off the stack
Don’t worry about why an item is off the stack, why the array didn’t delete that item, the next time you put it on the stack it will automatically overwrite, so don’t bother or do anything stupid.
Since the process is so simple, I don’t think I need much explanation.
Code implementation:
package com.xn2001.stack;
import java.util.Scanner;
public class ArrayStackDemo {
public static void main(String[] args) {
// Test ArrayStack to see if it works
// Create an ArrayStack object -> to represent the stack
ArrayStack stack = new ArrayStack(4);
String key = "";
boolean loop = true;
// Control whether to exit the menu
Scanner scanner = new Scanner(System.in);
while (loop) {
System.out.println("Show: display stack");
System.out.println("Exit: Exit the program");
System.out.println("Push: to add data to the stack (push)");
System.out.println("Pop: takes data off the stack (out of the stack)");
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 data out of the stack is %d\n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case "exit":
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("Program exit ~~~"); }}class ArrayStack {
private int maxSize; // Stack size
private int[] stack; // Array, array emulation stack
private int top = -1; // top of stack, initialized to -1
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new int[this.maxSize];
}
public boolean isFull(a) {
return top == maxSize - 1;
}
public boolean isEmpty(a) {
return top == -1;
}
/ / into the stack - push
public void push(int value) {
if (isFull()) {
System.out.println("Stack full");
return;
}
top++;
stack[top] = value;
}
/ / the stack - pop
public int pop(a) {
if (isEmpty()) {
throw new RuntimeException("Stack empty, no data ~");
}
int value = stack[top];
top--;
return value;
}
// display stack condition [traversal stack], traversal, need to display data from the top of the stack
public void list(a) {
if (isEmpty()) {
System.out.println("Stack empty, no data.");
return;
}
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n", i, stack[i]); }}}Copy the codeStack implementation Comprehensive Calculator (infix expression)
Implementation idea:
- Create two stacks, one for values and one for operators
- Parse the expression, using a variable of type char, and push the expression onto the stack one by one
- Determine the precedence of the operator and the top of the stack before pressing the operator
- If the top priority of the stack is higher, it is directly calculated, the purpose: to make its final addition and subtraction, it is very comfortable. For example: 3+3*3+3, when pressing the second “+”, judge that the priority is lower than *****, then calculate 3×3 first. And push the + on the stack.
- And then we’re left with 3+9+3, two numbers from the value stack, one symbol from the operator stack. We can add and subtract. The result is pushed back into the stack for the next calculation.
- Minus sign to pay attention to negative numbers, primary knowledge. I have explained the details in the code.
- You end up with an empty operator stack and a single number in the stack, and that’s what you end up with.
Code implementation:
package com.xn2001.stack;
public class Calculator {
public static void main(String[] args) {
String expression = "2-2 * 2 + 5";
// Create two stacks, one for numbers and one for symbols
ArrayStack2 numStack = new ArrayStack2(10);
ArrayStack2 operStack = new ArrayStack2(10);
int index = 0;
int num1 = 0;
int num2 = 0;
int oper = 0;
int res = 0;
char ch = ' ';
String keepNum = "";
do {
// Get each character of expression in turn
ch = expression.substring(index, index + 1).charAt(0);
// Determine what ch is, and then do something about it
if (operStack.isOper(ch)) {
if(! operStack.isEmpty()) {If the current operator has a priority less than or equal to that of the operator in the stack, pop two numbers from the stack
// Pop a symbol from the symbol stack, perform an operation, get the result, add the number stack, and then add the current operator 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); numStack.push(res); }}// add to symbol stack
operStack.push(ch);
} else {
//1. When processing a number of digits, it cannot be immediately pushed because it may be a number of digits
//2. When processing numbers, we need to look at the index of expression. If it is a number, we scan it; if it is a symbol, we stack it
//3. So we need to define a variable string for concatenation
// Process multiple digits
keepNum += ch;
if (index == expression.length() - 1) {
numStack.push(Integer.parseInt(keepNum));
} else {
// Determine if the next character is a number, if it is a number, continue scanning, if it is an operator, push
if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
// If the last bit is an operator, push keepNum = "1" or "123"
numStack.push(Integer.parseInt(keepNum));
keepNum = "";
}
}
}
index++;
// make index+1 and check if the last expression is scanned
} while (index < expression.length());
// In the last loop, there is only addition and subtraction!
while(! operStack.isEmpty()) {// If the symbol stack is empty, the final result is computed and there is only one number in the stack
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
// perform subtraction instead of addition when preceded by a minus sign.
if(! operStack.isEmpty() && operStack.peek() ==The '-') {
oper = operStack.peek();
}
res = numStack.cal(num1, num2, oper);
numStack.push(res);
}
int res2 = numStack.pop();
System.out.printf(Expression %s = %d, expression, res2); }}class ArrayStack2 {
private int maxSize; // Stack size
private int[] stack; // Array, array emulation stack
private int top = -1; // top of stack, initialized to -1
public ArrayStack2(int maxSize) {
this.maxSize = maxSize;
stack = new int[this.maxSize];
}
/ / stack
public int peek(a) {
return stack[top];
}
public boolean isFull(a) {
return top == maxSize - 1;
}
public boolean isEmpty(a) {
return top == -1;
}
/ / into the stack - push
public void push(int value) {
if (isFull()) {
System.out.println("Stack full");
return;
}
top++;
stack[top] = value;
}
/ / the stack - pop
public int pop(a) {
if (isEmpty()) {
throw new RuntimeException("Stack empty, no data ~");
}
int value = stack[top];
top--;
return value;
}
// display stack condition [traversal stack], traversal, need to display data from the top of the stack
public void list(a) {
if (isEmpty()) {
System.out.println("Stack empty, no data.");
return;
}
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n", i, stack[i]); }}// Returns the operator's priority, which is defined by the programmer and expressed as a number
// The larger the number, the higher the priority
public int priority(int oper) {
if (oper == The '*' || oper == '/') {
return 2;
} else if (oper == '+' || oper == The '-') {
return 1;
} else {
return -1; // Leave out the parentheses for now}}// Determine if it is an operator
public boolean isOper(char val) {
return val == '+' || val == The '-' || val == The '*' || val == '/';
}
// Calculate method
public int cal(int num1, int num2, int oper) {
int res = 0;
switch (oper) {
case '+':
res = num1 + num2;
break;
case The '-':
res = num2 - num1; Num2 = 5; num2 = 5
break;
case The '*':
res = num1 * num2;
break;
case '/':
res = num2 / num1;
break;
default:
break;
}
returnres; }}Copy the codeInverse Polish calculator
An inverse Polish expression, normally called a postfix expression, follows the operand.
For example, (3+4)×5-6 is 3, 4 + 5 × 6 –
How about if you convert? We’ll talk about that later. Here you need to understand the basic concepts of prefix and infix expressions.
Infix expressions are common operation expressions, such as (3+4)×5-6; A prefix expression is the reverse of a suffix.
The evaluation of infix expression is the most familiar to us, but it is not good for computers to operate (we can see this problem in the previous cases), so when calculating the result, the infix expression is often converted into other expressions to operate (generally converted into suffix expression).
Analysis of ideas:
The suffix expression corresponding to (3+4)×5-6 is 3, 4 + 5 × 6 -. The procedure for evaluating the suffix expression is as follows:
- Scan from left to right, pushing 3 and 4 onto the stack;
- The + operator is encountered, so pop 4 and 3 (4 is the top element, 3 is the second top element), evaluate 3+4, get 7, and push 7 onto the stack;
- Push 5;
- Next comes the × operator, so pop up 5 and 7, calculate 7×5=35, and push 35;
- Push 6;
- Finally, the – operator computes the value of 35-6, or 29, from which the final result is obtained
Code implementation:
package com.xn2001.stack;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
public class PolandNotation {
public static void main(String[] args) {
// Define the inverse Polish expression first
// (30+4)×5-6 => 30 4 + 5 × 6 - => 164
// 4 * 5-8 + 60 + 8/2 => 4 5 * 8-60 + 8 2 / +
String suffixExpression = 4 5 * 8-60 + 8 2 / +;
//1. Add "3 4 + 5 × 6 - "=> to ArrayList
//2. Pass the ArrayList to a method that iterates through the ArrayList with the stack to complete the calculation
List<String> rpnList = getListString(suffixExpression);
System.out.println(rpnList);
int res = calculate(rpnList);
System.out.println("The result of the calculation is" + res);
}
// An inverse Polish expression is used to place the data and operators in turn into the ArrayList
public static List<String> getListString(String suffixExpression) {
// Cut according to space
String[] split = suffixExpression.split("\\s+");
return new ArrayList<>(Arrays.asList(split));
}
/* * Complete the inverse Polish expression * 1) scan from left to right, pushing 3 and 4 onto the stack; * 2) The + operator is encountered, so pop 4 and 3 (4 is the top element, 3 is the second top element), calculate the value of 3+4, get 7, and push 7 onto the stack; * 3) Push 5 onto the stack; * 4) Next comes the × operator, so pop 5 and 7, calculate 7×5=35, and push 35 onto the stack; * 5) Push 6; * 6) Finally, the - operator computes the value of 35-6, or 29, from which the final result */ is obtained
public static int calculate(List<String> ls) {
/ / create a stack
Stack<String> stack = new Stack<>();
for (String l : ls) {
// Match multiple digits
if (l.matches("\\d+")) {
stack.push(l);
} else {
int num2 = Integer.parseInt(stack.pop());
int num1 = Integer.parseInt(stack.pop());
int res = 0;
switch (l) {
case "+":
res = num1 + num2;
break;
case "-":
res = num1 - num2;
break;
case "*":
res = num1 * num2;
break;
case "/":
res = num1 / num2;
break;
default:
System.out.println(l.toString());
throw new RuntimeException("Operator error");
}
// push res onto the stack
stack.push(res + ""); }}returnInteger.parseInt(stack.pop()); }}Copy the codeInfix expressions are converted to postfix expressions
Suffix expression is suitable for calculation, but it is not easy for ordinary people to write out, especially the expression is very long, so in the development of the program, we need to change the infix expression into suffix expression.
Specific ideas are as follows:
- Initialize two stacks: the operator stack S1 and the intermediate result stack S2;
- Scan infix expressions from left to right;
- When it encounters an operand, it presses s2;
- When an operator is encountered, it is compared with the priority of the S1 top-stack operator
- If s1 is empty, or the top of the s1 stack operator is an open parenthesis “(“, the operator is pushed directly onto the stack.
- Otherwise, if the priority is higher than the top of the stack, push the operator into S1;
- Otherwise, pop the s1 top stack operator and push it into S2, and go to step 4-1 again to compare it with the new top stack operator in S1;
- When I encounter parentheses
- If the opening parenthesis is “(“, the s1 is pressed directly
- In the case of the close parenthesis “) “, the top s1 operator is successively popped and pushed into S2 until the open parenthesis is encountered, at which point the parenthesis pair is discarded.
- Repeat steps 2 through 5 to the far right of the expression.
- The remaining operators in S1 are ejected and pressed into S2 in turn
- Pop up elements in S2 in turn and output, and the reverse order of the result is the suffix expression corresponding to the infix expression
For example, the infix expression “1 +((2+3)×4)-5 “is converted to the suffix expression “1 2 3 + 4 × + 5 -“.
Code implementation (combined with the previous calculator code, we have a complete implementation of a calculator)
package com.xn2001.stack;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
public class PolandNotation {
public static void main(String[] args) {
String expression = "1 + (2 + 3) * 4) - 5";
List<String> infixExpressionList = toInfixExpressionList(expression);
System.out.println("List of infix expressions:" + infixExpressionList); //[1, +, (, (, 2, +, 3,), *, 4,), -, 5]
List<String> parseSuffixExpressionList = parseSuffixExpreesionList(infixExpressionList);
System.out.println("Postfix expression corresponding to List:" + parseSuffixExpressionList); //[1, 2, 3, +, 4, *, +, 5, -]
int calculate = calculate(parseSuffixExpressionList);
System.out.printf("expression = %d", calculate);
// (30+4)×5-6 => 30 4 + 5 × 6 - => 164 // 4 * 5-8 + 60 + 8/2 => 4 5 * 8-60 + 8 2 / + String suffixExpression = "4 5 * 8 - 60 + 8 2 / +"; //1. Add "3 4 + 5 × 6 - "=> to ArrayList. List
rpnList = getListString(suffixExpression); System.out.println(rpnList); int res = calculate(rpnList); System.out.println(" the result is "+ res); * /
}
// Method: the List corresponding to the infix expression => the List corresponding to the postfix expression
public static List<String> parseSuffixExpreesionList(List<String> ls) {
// Define two stacks
Stack<String> s1 = new Stack<>(); / / symbol stack
// Note: there is no pop operation in s2 stack during the whole conversion process, and we need reverse output later
List
s2 instead of Stack
List<String> s2 = new ArrayList<>(); // Stack s2 for intermediate results
for (String item : ls) {
// If it is a number, add s2
if (item.matches("\\d+")) {
s2.add(item);
} else if (item.equals("(")) {
s1.push(item);
} else if (item.equals(")")) {
while(! s1.peek().equals("(")) {
s2.add(s1.pop());
}
s1.pop(); // Pop the "(", eliminating the parentheses
} else {
// When the priority of item is less than or equal to the priority of the top stack operator
while(s1.size() ! =0 && !s1.peek().equals("(") && Operation.getValue(s1.peek()) >= Operation.getValue(item)) { s2.add(s1.pop()); } s1.push(item); }}// Pop the remaining operators in S1 and add s2
while(s1.size() ! =0) {
s2.add(s1.pop());
}
return s2;
}
// Method: convert infix expression to corresponding List
public static List<String> toInfixExpressionList(String s) {
List<String> ls = new ArrayList<>();
int i = 0; // a pointer to iterate over the infix expression string;
String str; // Concatenation of multiple digits
char c;
do {
// If c is a non-number, add it to ls
if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
ls.add("" + c);
i++;
} else {
str = ""; // set STR to "" '0'[48]->'9'[57]
while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
str += c;/ / stitchingi++; } ls.add(str); }}while (i < s.length());
return ls;
}
// An inverse Polish expression is used to place the data and operators in turn into the ArrayList
public static List<String> getListString(String suffixExpression) {
// Cut according to space
String[] split = suffixExpression.split("\\s+");
return new ArrayList<>(Arrays.asList(split));
}
/* * Complete the inverse Polish expression * 1) scan from left to right, pushing 3 and 4 onto the stack; * 2) The + operator is encountered, so pop 4 and 3 (4 is the top element, 3 is the second top element), calculate the value of 3+4, get 7, and push 7 onto the stack; * 3) Push 5 onto the stack; * 4) Next comes the × operator, so pop 5 and 7, calculate 7×5=35, and push 35 onto the stack; * 5) Push 6; * 6) Finally, the - operator computes the value of 35-6, or 29, from which the final result */ is obtained
public static int calculate(List<String> ls) {
/ / create a stack
Stack<String> stack = new Stack<>();
for (String l : ls) {
// Match a number
if (l.matches("\\d+")) {
stack.push(l);
} else {
int num2 = Integer.parseInt(stack.pop());
int num1 = Integer.parseInt(stack.pop());
int res = 0;
switch (l) {
case "+":
res = num1 + num2;
break;
case "-":
res = num1 - num2;
break;
case "*":
res = num1 * num2;
break;
case "/":
res = num1 / num2;
break;
default:
System.out.println(l.toString());
throw new RuntimeException("Operator error");
}
// push res onto the stack
stack.push(res + ""); }}returnInteger.parseInt(stack.pop()); }}// Write a class Operation that returns the priority of an operator
class Operation {
private static int ADD = 1;
private static int SUB = 1;
private static int MUL = 2;
private static int DIV = 2;
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 operator does not exist");
break;
}
returnresult; }}Copy the code