# Introduction to stack

Stack is an orderly list of first in first out (FILO). The first data is placed at the bottom of the stack, the last element is placed at the top of the stack, the last element is deleted first, and the first one is deleted first.

# Stack implementation

```public class Stack {
private int[] stack;
private int top;
private int maxSize;
public Stack(int maxSize){
this.stack=new int[maxSize];
this.maxSize=maxSize;
this.top=0;
}

public boolean isFull(){
}

public boolean isEmpty(){
}

public boolean push(int value){
if(isFull()) return false;
this.stack[top]=value;
top++;
return true;
}

public Integer pop(){
if(isEmpty()) return null;
int value=stack[top];
top--;
return value;
}
}
```

# Calculation of infix expression

## Algorithmic thinking

For example, calculation: 3 + 2 * 6-2
The algorithm steps are as follows:
Maintain 2 stacks digital stack and symbol stack

1. Scan from front to back, if you encounter numbers, directly enter the digital stack.
2. If symbols are encountered, they can be divided into the following three situations:
• If the symbol stack is empty, push it directly into the stack.
• If the symbol stack is not empty and the symbol priority is less than or equal to the top element of the stack, pop will perform two numerical operations, and then re stack the result.
• If the symbol stack is not empty and the symbol priority is greater than the top element of the stack, the symbol is directly pushed into the stack

## code implementation

Address of Niuke: https://www.nowcoder.com/questionterminal/7b18aa6b7cc14f8eaae6b8acdeb890b? Tocommentid = 103161

```import java.util.Scanner;
import java.util.Stack;

public class Main {
public static void main(String[] args) throws Exception {
Scanner cin = new Scanner(System.in);
Main m=new Main();
while (cin.hasNext()){
String exp=cin.next();
float res=m.nifix(exp);
System.out.println((int)res);
}

}
public float nifix(String expression){
Stack<Float> numberStack=new Stack<>();
Stack<Character> symbolStack=new Stack<>();
String digit="";
for(int i=0;i<expression.length();i++){
char x=expression.charAt(i);
if(Character.isDigit(x)){
digit+=String.valueOf(x);
if(i+1>=expression.length()||!Character.isDigit(expression.charAt(i+1))){
numberStack.push(Float.parseFloat(digit));
digit="";
}

}else {
while (!symbolStack.isEmpty()&&priority(symbolStack.peek())>=priority(x)){
char y=symbolStack.pop();
float res=calRes(y,numberStack.pop(),numberStack.pop());
numberStack.push(res);
}
symbolStack.push(x);
}
}
while (!symbolStack.isEmpty()){
char y=symbolStack.pop();
float res=calRes(y,numberStack.pop(),numberStack.pop());
numberStack.push(res);
}
return numberStack.pop();
}
//Determine the priority of symbols
private int priority(char x){
if(x =='+'|| x =='-'){
return 1;
}else{
return 2;
}

}
//Calculation results
private float calRes(char x,float num1,float num2){
float res=0;
switch (x){
case '+':
res=num1+num2;
break;
case '-':
res=num2-num1;
break;
case '*':
res=num1*num2;
break;
case '/':
res=num2/num1;
break;
}
return res;

}
}
```

# Suffix expression evaluation

## Algorithmic thinking

Example of suffix expression:
The suffix expression corresponding to (3+4)x5-6 is 34+5x6 -.
Computer processing suffix expression is very direct, maintenance of a stack can complete the calculation.

## code implementation

```import java.util.Scanner;
import java.util.Stack;

public class Main {
public static void main(String[] args) throws Exception {
Scanner cin = new Scanner(System.in);
Main m=new Main();
while (cin.hasNext()){
String exp=cin.next();
float res=m.postfix(exp);
System.out.println((int)res);
}

}
public float postfix(String expression){
String[] expressionItem=expression.split(" ");
Stack<Float> stack=new Stack<>();
for(int i=0;i<expressionItem.length;i++){
String item=expressionItem[i];
if(isNumeric(item)){
stack.push(Float.parseFloat(item));
}else {
stack.push(cal(item,stack.pop(),stack.pop()));
}

}
return stack.pop();
}
private static boolean isNumeric(String str){
for (int i = str.length();--i>=0;){
if (!Character.isDigit(str.charAt(i))){
return false;
}
}
return true;
}
//Calculation results
private float cal(String item,float num1,float num2){
float res=0;
if(item.equals("+")){
res=num2+num1;
}else if(item.equals("-")){
res=num2-num1;
}else if(item.equals("/")){
res=num2/num1;
}else if(item.equals("*")){
res=num2*num1;
}
return res;

}
}
```

# Infix expression to suffix expression

Limit must be 1 digit
Input:
a+bc/d-a+f/b
Output:
abcd/+a-fb/+

## Algorithmic thinking

• Scan infix expressions from left to right
• Add suffix expression when a number is encountered
• When an operator is encountered:
a. If '(', stack
b. If it is') ', the operators in the stack will be added to the suffix expression in turn until' ('appears and' is deleted from the stack '('
c. If it is an operator other than the bracket, when the priority is higher than the stack top operator other than '(', it will be directly pushed into the stack; otherwise, from the top of the stack, the operators with higher priority and equal priority than the currently processed operators will pop up in turn until a lower priority or a left bracket is encountered.

## code implementation

```import java.util.Scanner;
import java.util.Stack;

public class Main {
public static void main(String[] args) throws Exception {

Scanner cin = new Scanner(System.in);
Main m = new Main();
while (cin.hasNext()) {
String exp = cin.next();
String res = m.niToPost(exp);
System.out.println(res);
}
}

//Judge whether it is a number
private static boolean isNumeric(char c) {
if (c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')')
return false;
return true;
}

public String niToPost(String expression) {
char[] res = new char[expression.length()];
int index = 0;
Stack<Character> symbolStack = new Stack<>();
for (int i = 0; i < expression.length(); i++) {
char x = expression.charAt(i);
if (isNumeric(x)) {
res[index] = x;
index++;
} else if (x == '(') {
symbolStack.push(x);
} else if (x == ')') {
while (symbolStack.peek() != '(') {
res[index] = symbolStack.pop();
index++;
}
symbolStack.pop();
} else {
while (!symbolStack.isEmpty() && symbolStack.peek() != '(' && priority(symbolStack.peek()) >= priority(x)) {
res[index] = symbolStack.pop();
index++;
}
symbolStack.push(x);
}

}
while (!symbolStack.isEmpty()) {
res[index] = symbolStack.pop();
index++;
}
return String.valueOf(res);
}

//Determine the priority of symbols
private int priority(char x) {

if (x == '+' || x == '-') {
return 1;
} else if (x == '*' || x == '/') {
return 2;
}
return 0;
}
}

```
Published 38 original articles, won praise 1, visited 784

Tags: Java less

Posted on Thu, 06 Feb 2020 05:19:51 -0800 by jmajeremy