栈是一个先入后出 (FILO-FirstInLastOut) 的有序列表。
栈是限度线性表中元素的插入和删除只能在线性表的同一端进行的一种非凡线性表。容许插入和删除的一端，为变动的一端，称为栈顶 (Top)，另一端为固定的一端，称为栈底(Bottom)。
依据栈的定义可知，最先放入栈中元素在栈底，最初放入的元素在栈顶，而删除元素刚好相同，最初放入的元素最先删除，最先放入的元素最初删除。
public class ArrayStackDemo {public static void main(String[] args) {ArrayStack stack = new ArrayStack(5);
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
stack.list();
stack.pop();
stack.list();}
}
// 定义一个 ArrayStack 示意栈
class ArrayStack {
private int maxSize; // 栈的大小
private int[] stack; // 数组，数组模仿栈，数据就放在该数组
private int top = -1;// top 示意栈顶，初始化为 -1
// 结构器
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new int[this.maxSize];
}
// 栈满
public boolean isFull() {return top == maxSize - 1;}
// 栈空
public boolean isEmpty() {return top == -1;}
// 入栈 -push
public void push(int value) {
// 先判断栈是否满
if(isFull()) {System.out.println("栈满");
return;
}
top++;
stack[top] = value;
}
// 出栈 -pop, 将栈顶的数据返回
public int pop() {
// 先判断栈是否空
if(isEmpty()) {
// 抛出异样
throw new RuntimeException("栈空，没有数据~");
}
int value = stack[top];
top--;
return value;
}
// 显示栈的状况[遍历栈]，遍历时，须要从栈顶开始显示数据
public void list() {if(isEmpty()) {System.out.println("栈空，没有数据~~");
return;
}
// 须要从栈顶开始显示数据
for(int i = top; i >= 0 ; i--) {System.out.println(String.valueOf(stack[i]));
}
}
}
中断表达式实现计算器
思路剖析：
筹备两个栈，一个存数，一个存运算符
1. 通过一个 index 值遍历表达式
2. 如果发现以后是一个数字，间接入数栈
3. 如果发现以后是一个符号
如果以后符号栈为空，入符号栈
如果以后符号栈不为空
如果以后操作符的优先级小于或者等于栈中操作符，则先不入 符号栈，须要从数栈中 pop 出两个数，从符号栈中 pop 出一个 符号，进行运算，失去后果，入数栈，再将以后操作符入符号 栈
如果以后操作符的优先级大于栈中操作符，间接入符号栈4. 当表达式扫描结束，就程序从数栈和符号栈中 pop 出相应的数和符号，并运行
5. 数栈中只有一个数字，就是表达式的后果
package com.example.demo;
public class Calculator {public static void main(String[] args) {
String expression = "70*2*2-5+1-5+3-4";
// 创立两个栈，数栈，一个符号栈
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 = ' '; // 将每次扫描失去 char 保留到 ch
String keepNum = ""; // 用于拼接多位数
// 开始 while 循环的扫描 expression
while(true) {
// 顺次失去 expression 的每一个字符
ch = expression.substring(index, index+1).charAt(0);
// 判断 ch 是什么，而后做相应的解决
if(operStack.isOper(ch)) {// 如果是运算符
// 判断以后的符号栈是否为空
if(!operStack.isEmpty()) {
// 如果符号栈有操作符，就进行比拟, 如果以后的操作符的优先级小于或者等于栈中的操作符, 就须要从数栈中 pop 出两个数,
// 在从符号栈中 pop 出一个符号，进行运算，将失去后果，入数栈，而后将以后的操作符入符号栈
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);
// 而后将以后的操作符入符号栈
operStack.push(ch);
} else {
// 如果以后的操作符的优先级大于栈中的操作符，就间接入符号栈.
operStack.push(ch);
}
}else {
// 如果为空间接入符号栈
operStack.push(ch);
}
} else { // 如果是数，则间接入数栈
// 剖析思路
//1. 当解决多位数时，不能发现是一个数就立刻入栈，因为他可能是多位数
//2. 在解决数，须要向 expression 的表达式的 index 后再看一位, 如果是数就进行扫描，如果是符号才入栈
//3. 因而咱们须要定义一个变量 字符串，用于拼接
// 解决多位数
keepNum += ch;
// 如果 ch 曾经是 expression 的最初一位，就间接入栈
if (index == expression.length() - 1) {numStack.push(Integer.parseInt(keepNum));
}else{
// 判断下一个字符是不是数字，如果是数字，就持续扫描，如果是运算符，则入栈
// 留神是看后一位，不是 index++
if (operStack.isOper(expression.substring(index+1,index+2).charAt(0))) {
// 如果后一位是运算符，则入栈
numStack.push(Integer.parseInt(keepNum));
// 重要的!!!!!!, keepNum 清空
keepNum = "";
}
}
}
// 让 index + 1, 并判断是否扫描到 expression 最初.
index++;
if (index >= expression.length()) {break;}
}
// 当表达式扫描结束，就程序的从 数栈和符号栈中 pop 出相应的数和符号，并运行.
while(true) {
// 如果符号栈为空，则计算到最初的后果, 数栈中只有一个数字【后果】if(operStack.isEmpty()) {break;}
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1, num2, oper);
numStack.push(res);// 入栈
}
// 将数栈的最初数，pop 出，就是后果
int res2 = numStack.pop();
System.out.printf("表达式 %s = %d", expression, res2);
}
}
// 定义一个 ArrayStack2 示意栈, 须要扩大性能
class ArrayStack2 {
private int maxSize; // 栈的大小
private int[] stack; // 数组，数组模仿栈，数据就放在该数组
private int top = -1;// top 示意栈顶，初始化为 -1
// 结构器
public ArrayStack2(int maxSize) {
this.maxSize = maxSize;
stack = new int[this.maxSize];
}
// 减少一个办法，能够返回以后栈顶的值, 然而不是真正的 pop
public int peek() {return stack[top];
}
// 栈满
public boolean isFull() {return top == maxSize - 1;}
// 栈空
public boolean isEmpty() {return top == -1;}
// 入栈 -push
public void push(int value) {
// 先判断栈是否满
if(isFull()) {System.out.println("栈满");
return;
}
top++;
stack[top] = value;
}
// 出栈 -pop, 将栈顶的数据返回
public int pop() {
// 先判断栈是否空
if(isEmpty()) {
// 抛出异样
throw new RuntimeException("栈空，没有数据~");
}
int value = stack[top];
top--;
return value;
}
// 显示栈的状况[遍历栈]，遍历时，须要从栈顶开始显示数据
public void list() {if(isEmpty()) {System.out.println("栈空，没有数据~~");
return;
}
// 须要从栈顶开始显示数据
for(int i = top; i >= 0 ; i--) {System.out.printf("stack[%d]=%d\n", i, stack[i]);
}
}
// 返回运算符的优先级，优先级是程序员来确定, 优先级应用数字示意
// 数字越大，则优先级就越高.
public int priority(int oper) {if(oper == '*' || oper == '/'){return 1;} else if (oper == '+' || oper == '-') {return 0;} else {return -1; // 假设目前的表达式只有 +, - , * , /}
}
// 判断是不是一个运算符
public boolean isOper(char val) {return val == '+' || val == '-' || val == '*' || val == '/';}
// 计算方法
public int cal(int num1, int num2, int oper) {
int res = 0; // res 用于寄存计算的后果
switch (oper) {
case '+':
res = num1 + num2;
break;
case '-':
res = num2 - num1;// 留神程序
break;
case '*':
res = num1 * num2;
break;
case '/':
res = num2 / num1;
break;
default:
break;
}
return res;
}
}
逆波兰表达式
(3+4)×5-6 对应的后缀表达式就是 34+5 × 6-, 针对后缀表达式求值步骤如下:
1．从左至右扫描，将 3 和 4 压入堆栈；
2．遇到 + 运算符，因而弹出 4 和 3（4 为栈顶元素，3 为次顶元素），计算出 3+4 的值，得 7，再将 7 入栈；
3．将 5 入栈；
4．接下来是×运算符，因而弹出 5 和 7，计算出 7×5=35，将 35 入栈；
5．将 6 入栈；
6．最初是 - 运算符，计算出 35-6 的值，即 29，由此得出最终后果
中断表达式转后缀表达式
//TODO