- 2020-05-18 15:31
*views 3*- Data structure and algorithm

One , Stack

Stack （stack） Also known as stack , It is a linear table with limited operation . A linear table that restricts insertion and deletion operations only at the end of the table . This end is called the top of the stack , Relatively , Call the other end the bottom of the stack . Inserting new elements into a stack is also called stack entry , Put or press the stack , It puts new elements on top of the top of the stack , Make it a new top of stack element ; Deleting elements from a stack is also called stack exit or stack exit , It is to delete the top element of the stack , Make its adjacent elements new top of stack elements .

Two , Application scenarios of stack

1, Subroutine call

Before calling to subroutine , The address of the next instruction is first put on the stack , The address will not be thrown until the subroutine is executed , To go back to the original procedure .

2, Handling recursive calls

Similar to subroutine call , Except for the address of the next instruction , Also store parameters , Regional variables and other data .

3, Expression conversion

Infix expression to suffix expression

4, Traversal of binary tree

5, Depth first search method for graphics

Three , Stack implementation of comprehensive calculator （ Infix expression ）

1, Thinking analysis

* Through a index value （ Indexes ）, To traverse our expressions

* If it is found to be a number, put it directly into the stack

* If the current symbol stack is found to be empty , Just go straight to the stack

*

If the symbol stack is found to have an operator , We'll make a comparison , If the priority of the current operator is less than or equal to the operator in the stack , You need to start from the stack pop Make a symbol , Do the operation , You'll get the results , Input data stack , Then put the current operator on the symbol stack , If the priority of the current operator is higher than that of the stack operator , Just go straight to the symbol stack .

* When the expression is scanned , In order from the number stack and symbol stack pop The corresponding numbers and symbols are given , And calculate .

* Finally, there is only one number in the stack , This is the result of the expression .

2, Code instance

（1）ArrayStack Tools

package dataStructure.stack; public class ArrayStack { private int maxSize; //

Stack size private int[] stack; // array , Array emulation stack , The data is placed in the array private int top = -1;//

top Represents the top of the stack , Initialize to -1 // constructor public ArrayStack(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 not really pop public int

peek() { return stack[top]; } // Stack full public boolean isFull() { return top ==

maxSize - 1; } // Stack empty public boolean isEmpty() { return top == -1; } // Push -push

public void push(int value) { // First judge whether the stack is full if(isFull()) {

System.out.println(" Stack full "); return; } top++; stack[top] = value; } // Out of the stack -pop,

Return the data at the top of the stack public int pop() { // First judge whether the stack is empty if(isEmpty()) { // Throw an exception throw new

RuntimeException(" Stack empty , no data ~"); } int value = stack[top]; top--; return value; }

// Show the stack [ Traversal stack ], Traversal time , You need to display data from the top of the stack public void list() { if(isEmpty()) {

System.out.println(" Stack empty , no data ~~"); return; } // You need to display data 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 , Priority is determined by the programmer , Priority is expressed in numbers // The bigger the number is , 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 has only +, - , * , / } }

// Determine whether 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 It is used to store the results of calculation switch (oper) { case '+': res = num1 +

num2; break; case '-': res = num2 - num1;// Pay attention to the order break; case '*': res = num1 *

num2; break; case '/': res = num2 / num1; break; default: break; } return res;

} }

（2） Test class

package dataStructure.stack; public class Calculator { public static void

main(String[] args) { // According to the teacher's ideas , Complete the operation of the expression String expression = "100/5+2*3-1"; //

25 // Create two stacks , Counting stack , A symbol stack ArrayStack numStack = new ArrayStack(10); ArrayStack

operStack = new ArrayStack(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 = ' '; // Each scan will get char Save to ch

String keepNum = ""; // For splicing Multibit number // start while Cyclic scanning expression while (true) {

// In turn expression Each character of the ch = expression.substring(index, index + 1).charAt(0);

// judge ch What is it? , Then do the corresponding treatment if (operStack.isOper(ch)) {// If it is an operator // Determine whether the current symbol stack is empty if

(!operStack.isEmpty()) {

// If the symbol stack has an operator , We'll make a comparison , If the priority of the current operator is less than or equal to the operator in the stack , You need to start from the stack pop Give two numbers ,

// From the symbol stack pop Make a symbol , Do the operation , You'll get the results , Input data stack , Then put the current operator on 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 the operation is counted as a stack numStack.push(res); // Then put the current operator on the symbol stack operStack.push(ch); } else {

// If the priority of the current operator is higher than that of the stack operator , Just go straight to the symbol stack . operStack.push(ch); } } else { // If it is empty, direct access to symbol stack ..

operStack.push(ch); // 1 + 3 } } else { // If it's a number , Then it is directly put into the data stack //numStack.push(ch - 48);

//? "1+3" '1' => 1 // Analysis ideas //1. When dealing with multiple bits , If you can't find a number, put it on the stack immediately , Because he may be a multi digit //2.

In process number , Need to expression Of the expression index I'll see another one later , If it's a number, scan it , If it's a symbol, it's on the stack //3. So we need to define a variable

character string , For splicing // Processing multiple bits keepNum += ch; // If ch Already expression Last of all , Just go straight to the stack if (index ==

expression.length() - 1) { numStack.push(Integer.parseInt(keepNum)); } else {

// Determine whether the next character is a number , If it's a number , Just keep scanning , If it is an operator , Then put it on the stack // Notice the last one , no index++ if

(operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {

// If the last bit is an operator , Then put it on the stack keepNum = "1" perhaps "123"

numStack.push(Integer.parseInt(keepNum)); // important !!!!!! keepNum empty keepNum = "";

} } } // Give Way index + 1, And judge whether to scan expression last . index++; if (index >=

expression.length()) { break; } } // When the expression is scanned , In order Number stack and symbol stack pop The corresponding numbers and symbols are given , And running .

while (true) { // If the symbol stack is empty , Then calculate to the final result , There is 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);// Push }

// Count the last number of the stack ,pop Out , That's the result int res2 = numStack.pop(); System.out.printf(" expression %s = %d",

expression, res2); } }

3, console output

Technology

- Java378 articles
- Python197 articles
- Linux110 articles
- MySQL83 articles
- Vue78 articles
- SpringBoot68 articles
- Spring61 articles
- javascript56 articles
- more...

Daily Recommendation

views 2

©2019-2020 Toolsou All rights reserved,

Bitcoin in ten years ,VDS Opportunity or fraud Don't annoy the panda with any cat !「 Kung Fu Panda 」20 It's the year of man 4 blood sort （ one ） bubble sort Random forest R Language implementation java Realize the function of grabbing red packets Python Basic knowledge and notes python To solve the problem of dictionary writing list in CSS architecture design Vue Common features （ one ）2021 year 2 Monthly programmer salary statistics , average 15144 element