java数据结构与算法学习_栈及栈的应用（计算器、中缀转后缀表达式）
栈
1）栈是一个先入后出的有序列表
2）栈是一种限制线性表，元素的插入和删除只在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端叫栈顶（Top），另一端为固定的一端叫栈底（bottom）
3）根据栈的定义可知，最先放入栈中的元素在栈底，最后放入的元素在栈顶。删除时，最后放入的元素最先删除，最先放入的元素最后删除。
栈的应用场景
1）子程序的调用：在跳往子程序前，会先将下个指令的地址存在堆栈中，直到子程序执行完毕后再将地址取出
2）处理递归调用：和子程序的调用类似，只是除了存储下一个指令的地之外，也将参数、区域变量等数据存储堆栈中
3）表达式的转换：中缀表达式转后缀表达式及求值
4）二叉树的遍历
5）图形的深度优先搜索法
实现栈的思路分析（数组实现）
1）使用一个数组来模拟栈
2）定义一个top来表示栈顶，初始化为-1
3）入栈的操作：当有数据加入到栈的时候，top++，stack[top] = data
4）出栈的操作：取出数据时，定义一个临时变量赋值栈顶元素，int temp = stack[top]; top–; return temp;
class ArrayStack{
private int maxSize;//栈的大小
private int[] stack;//栈的数据存入该数组
private int top = -1;//栈顶，初始化为-1
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
this.stack = new int[this.maxSize];
}
//栈满
public boolean isFull() {
return top == maxSize-1;
}
//栈空
public boolean isEmpty() {
return top == -1;
}
//入栈
public boolean push(int value) {
//先判断栈是否满
if(this.isFull()) {
return false;
}
else {
this.top++;
stack[this.top] = value;
return true;
}
}
//出栈:将栈顶的数据返回
public int pop() {
if(this.isEmpty()) {
throw new RuntimeException("栈为空,没有数据");
}
int value = this.stack[this.top];
this.top--;
return value;
}
//显示栈的情况【遍历栈】，遍历时，需要从栈顶开始显示数据
public void list() {
if(this.isEmpty()) {
System.out.println("栈为空，没有数据");
return;
}
for(int i = top; i > -1 ; i--) {
System.out.printf("stack[%d] = %d\n", i, this.stack[i]);
}
}
}
栈的应用
使用栈模拟计算器
实现思路
1）创建两个栈，一个存放数，一个存放符号
2）遍历表达式，判断每个字符是否为数字或符号
3）假定为数字，则直接入栈
4）假定为符号，有以下三种情况
4.1符号栈为空，则直接入栈
4.2当前符号和栈顶符号元素作比较，
优先级大于栈顶符号，则将当前符号入栈。
优先级小于栈顶符号，则从数字栈中取出两个数，从符号栈中取出一个符号进行计算。结果入数栈，当前扫描的符号入符号栈。
5）当表达式遍历结束，按顺序从数栈和符号栈中取出计算，将结果入栈
6）最终数栈最后一个数为结果
注：判断数字是否为多位数时，需要判断后一位是否为数字还是符号，如果为符号，则当前扫描到的数字可以入栈，如果不是，则需要继续扫描，并拼接。
代码实现
//栈结构
class MyStack{
private int[] arr;
private int top = -1;
private int maxSize;
public MyStack(int maxSize) {
this.maxSize = maxSize;
this.arr = new int[this.maxSize];
}
public boolean isFull() {
return this.top == this.maxSize-1;
}
public boolean isEmpty() {
return this.top == -1;
}
public boolean push(int value) {
if(this.isFull()) {
System.out.println("栈已满");
return false;
}
else{
this.top++;
this.arr[this.top] = value;
return true;
}
}
public int pop() {
if(this.isEmpty()) {
throw new RuntimeException("数组为空");
}
else {
int value = this.arr[this.top];
this.top--;
return value;
}
}
public void list() {
if(this.isEmpty()) {
throw new RuntimeException("数组为空");
}
else {
for(int i = top; i > -1 ; i--) {
System.out.println(this.arr[i]);
}
}
}
public int peek() {
return this.arr[top];
}
}
class Calculators{
private MyStack numStack;
private MyStack operStack;
public int val(String str) {
numStack = new MyStack(10);
operStack = new MyStack(10);
//将表达式变为字符数组
char[] chArr = str.toCharArray();
//定义需要的相关变量
int index = 0;//用于遍历
int num1 = 0;
int num2 = 0;
int res = 0;
int oper = 0;
String keepNum = "";
for(int i = 0 ; i < chArr.length ; i++) {
char ch = chArr[i];
//如果是符号，且符号栈为空 直接入栈
if(isOper(ch)) {
if(operStack.isEmpty()) {
operStack.push(ch);
}
else {
//判断符号优先级
if(priority(ch) <= priority(operStack.peek())) {
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = cal(num1, num2, oper);
numStack.push(res);
operStack.push(ch);
}
else {
operStack.push(ch);
}
}
}
//如果为数字
else {
keepNum += ch;
//numStack.push(ch - 48);
//如果是最后一位，则直接入栈
if(i == chArr.length-1) {
numStack.push(Integer.parseInt(keepNum));
}
//判断是否为多位数
else if(isOper(chArr[i+1])){
numStack.push(Integer.parseInt(keepNum));
//清空字符串
keepNum = "";
}
else {
continue;
}
}
}
while(true) {
//如果符号栈为空，则计算到最后的结果,数栈中只有一个数字为结果
if(operStack.isEmpty()) {
break;
}
else {
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = cal(num1, num2, oper);
numStack.push(res);
}
}
return numStack.pop();
}
public static boolean isOper(char val) {
return val == '+' || val == '-' || val == '*' || val == '/';
}
public static int priority(int oper) {
if(oper == '*' || oper == '/') {
return 1;
}
else if(oper == '+' || oper == '-') {
return 0;
}
else {
return -1;
}
}
public static int cal(int num1, int num2, int oper) {
int res = 0; //用于存放计数的结果
switch(oper) {
case '+':
res = num1 + num2;
break;
case '-':
//注意顺序
res = num2 - num1;
break;
case '*':
res = num2 * num1;
break;
case '/':
res = num2 / num1;
break;
}
return res;
}
}
public class CalculatorDemo {
public static void main(String[] args) {
String expression = "3+70*3-2";
Calculators cal = new Calculators();
int i = cal.val(expression);
System.out.println(i);
}
}
前缀表达式
又称波兰式，是指操作的运算符位于操作数前的表达式
1、计算机求值
从右向左扫描前缀表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶两个数，用运算符对它们做相应的计算（栈顶元素和次顶元素），并将结果入栈，重复过程直到表达式最左端，最后运算得出值
2、中缀表达式转前缀表达式方法
举例：1+（（2+3）×4）-5
1）首先确定表达式的运算顺序，然后加括号
（（1+（（2+3）×4））-5）
2）从最里面一层括号开始运算，转换成前缀表达式：具体为忽略括号，符号在前，数字在后
2+3 ----> +23
(2+3)×4 -----> ×+234
1+（（2+3）×4） -----> +1×+234
（1+（（2+3）×4））-5 -----> -+1×+2345
中缀表达式
最常见的运算表达式，但计算机不好操作，因此一般转为后缀来计算
后缀表达式
又称逆波兰表达式，与前缀表达式相似，只是运算符位于数字后面
1、计算机求值
从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们进行相应的计算（次顶元素和栈顶元素/次顶-栈顶）并将结果入栈，重复过程得出结果
2、中缀表达式转后缀表达式方法
举例：1+（（2+3）×4）-5
1）首先确定表达式的运算顺序，然后加括号
（（1+（（2+3）×4））-5）
2）从最里面一层括号开始运算，转换成前缀表达式：具体为忽略括号，符号在后，数字在前
2+3 ----> 23+
(2+3)×4 -----> 23+4×
1+（（2+3）×4） -----> 123+4×+
（1+（（2+3）×4））-5 -----> 123+4×+5-
3、后缀表达式计算代码实现
public class PolandCalculator {
public static void main(String[] args) {
//先定义给逆波兰表达式
//(3+4)*5-6 => 3 4 + 5 * 6 -;
//为了方便，逆波兰表达式的数字和符号使用空格隔开
String suffixExpression = "4 5 * 8 - 60 + 8 +";
List<String> list = getListString(suffixExpression);
int res = calculate(list);
System.out.println(res);
//思路
//1、先将“3 4 + 6 * 6 - ” 放到ArratList中
//2 将ArrayList 传递给一个方法，配合栈完成计算
}
//将一个逆波兰表达式，依次将数据和运算符放入到ArrayList中
public static List<String> getListString(String suffixExpression){
String[] split = suffixExpression.split(" ");
List<String> list = new ArrayList<String>();
for(String ele : split) {
list.add(ele);
}
return list;
}
public static int calculate(List<String> list) {
//创建栈，一个即可
Stack<String> stack = new Stack<String>();
for(String item : list) {
if(item.matches("\\d+")) {
stack.push(item);
}
else {
//如果不是数字，Pop出两个数，并运算
int num1 = Integer.parseInt(stack.pop()); //栈顶
int num2 = Integer.parseInt(stack.pop()); //栈第二个
int res = 0;
switch(item) {
case "+":
res = num2 + num1;
break;
case "-":
res = num2 - num1;
break;
case "*":
res = num2 * num1;
break;
case "/":
res = num2 / num1;
break;
default:
throw new RuntimeException("运算符有误");
}
stack.push(""+res);
}
}
return Integer.parseInt(stack.pop());
}
}
中缀表达式转后缀表达式
实现思路
1）初始化两个栈：运算符栈s1和存储中间结果的栈s2
2）从左到右扫描中缀表达式
3）遇到操作数时，将其压入s2
4）遇到运算符，比较其与s1栈顶运算符的优先级
4.1如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入s1栈
4.2若优先级比栈顶运算符高，也将运算符压入s1栈
4.3否则，将s1栈顶的运算符弹出并压入s2中，再次转到4.1，与s1中新栈顶元素运算符相比较
5）遇到括号时
5.1如果是左括号直接入栈s1
5.2如果是右括号，则依次弹出s1栈顶的运算符，并压入s2，直至遇到左括号为止，此时一对括号丢弃
6）重复步骤2至5，直到运算符的最后边
7）将s1中剩余的运算符依次弹出并压入s2
8）依次弹出s2中的元素并输出，将结果逆序，即为中缀表达式对应的后缀表达式
/*中缀表达式转后缀表达式
* 1、1+((2+3)*4)-5 => 1 2 3 + 4 * + 5 -
* 2、因为直接对str进行操作，不方便，因此将"1+((2+3)*4)-5" 中缀表达式对应的List
* 即"1+((2+3)*4)-5"=>Arraylist[1,+,(,(,2,+,3,),*,4,),-,5]
* 3、将中缀表达式转换为后缀表达式
* */
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 "DIV":
result = DIV;
break;
}
return result;
}
}
public class PolandDemo {
public static void main(String[] args) {
String suffeixExpression = "1+((2+3)*4)-5";
List<String> ls = toInfixExpressionList(suffeixExpression);
List<String> s2 = parseSuffixExpreesionList(ls);
int result = PolandCalculator.calculate(s2);
System.out.println(result);
}
public static List<String> toInfixExpressionList(String s){
//定义一个List，存放中缀表达式 对应的内容
List<String> ls = new ArrayList<String>();
String str = "";//多位数的拼接
char[] chArr = s.toCharArray();
for(int j = 0 ; j < chArr.length ; j++) {
str += chArr[j];
if(chArr[j] < 48 || chArr[j] > 57) {
ls.add(str);
}
else {
//考虑多位数
if(j == chArr.length-1) {
ls.add(str);
}
else{
if(chArr[j+1] >= 48 && chArr[j+1] <=57) {
continue;
}
else {
ls.add(str);
}
}
}
str = "";
}
return ls;
}
private static List<String> parseSuffixExpreesionList(List<String> ls) {
//定义两个栈s1 和s2
Stack<String> s1 = new Stack<String>();//符号栈
//因为没有pop操作所以直接使用List<String> 替代，可以直接逆序输出
//Stack<String> s2 = new Stack<String>();
List<String> s2 = new ArrayList<String>();
//开始遍历
for(String item: ls) {
//如果是一个数，直接入栈s2
if(item.matches("\\d+")) {
s2.add(item);
}
else if(item.equals("(") || s1.isEmpty()) {
s1.add(item);
}
else if(item.equals(")")){
while(true) {
String temp = s1.pop();
if(temp.equals("(")) {
break;
}
s2.add(temp);
}
}
else{
//当Item的优先级小于或等于栈顶的运算符，将s1的栈顶元素弹出压入s2
//在重新判断Item
//比较优先级的方法
while(s1.size()!=0 && (Operation.getValue(item) <= Operation.getValue(s1.peek()))) {
s2.add(s1.pop());
}
s1.add(item);
}
}
while(s1.size() != 0) {
s2.add(s1.pop());
}
return s2;
}
}
//结果为16
上一篇： 数据结构之循环队列和栈的应用
下一篇： 数据结构(08)_队列和栈的相互实现