首页 / 算法 / 数据结构和算法学习日记——栈
数据结构和算法学习日记——栈
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构和算法学习日记——栈,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含11133字,纯文字阅读大概需要16分钟。
内容图文
![数据结构和算法学习日记——栈](/upload/InfoBanner/zyjiaocheng/712/7b0b486d7a604d5cb9887de54f1ce9e6.jpg)
栈
栈是一个陷入后出的有序列表。
栈只能在表的一端进行添加和删除,不可对另一端进行操作,也不可在中间进行插入操作。
栈的可进行添加删除操作的一端被称为栈顶,另一端成为栈底。
栈有两种基本操作:出栈(pop)、入栈(push)
栈的应用场景
- 子程序 的调用
- 处理递归调用
- 表达式的转换(中缀表达式转换为后缀表达式)
- 二叉树的遍历
- 图的深度优先搜索
栈的简单实现
栈有两种基本的实现方式:数组、链表。
以下程序使用的是数组的实现方式:
public class SimpleStackDemo {
public static void main(String[] args) {
Stack s = new Stack(5);
s.push(0);
s.push(1);
s.push(2);
s.push(3);
s.push(4);
s.printStack();
s.push(5);
s.pop();
s.pop();
s.printStack();
s.pop();
s.pop();
s.pop();
s.pop();
}
}
class Stack {
private int[] stack = null;
private int size;
private int top = -1;
public Stack(int size) {
stack = new int[size];
this.size = size;
}
/**
* 判断栈是否为空
*/
public boolean isEmpty() {
return top == -1;
}
/**
* 判断栈是否满
*/
public boolean isFull() {
return top == size - 1;
}
/**
* 添加操作
*/
public void push(int data) {
if(isFull()) {
System.out.println("栈已满,不能添加新元素");
return;
}
top++;
stack[top] = data;
}
/**
* 弹出栈
*/
public int pop() {
if(isEmpty()) {
throw new RuntimeException("栈为空,无法弹出元素");
}
int val = stack[top];
top--;
return val;
}
/**
* 打印栈
*/
public void printStack() {
if(isEmpty()) {
System.out.println("栈空间为空");
return;
}
for(int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n", i, stack[i]);
}
}
}
栈实现综合表达式的计算
- 通过index对综合表达式的字符串进行遍历字符
- 将表达式中的数组压入到数字栈中,将运算符压入到操作符栈中
- 在第2步的过程中:如果将要压入栈的运算符的优先级低于栈顶中的操作符时,弹出数栈的两个数和运算符栈中的一个运算符,进行计算,将结果压入数栈中,最后再将新读取的运算符压入栈中。
- 当综合表达式遍历完后,再开始对两个栈中进行计算,最后得到结果
代码实现
public class StackDemo {
public static void main(String[] args) {
String str = "10+20 *8/4-2 =";
System.out.println("结果为:" + computer(str));
}
/**
* 获得综合公式的值
*/
public static int computer(String formula) {
//去除空格
formula = formula.replace(" ", "");
//去除等号
if(formula.charAt(formula.length() - 1) == '=') {
formula = formula.substring(0, formula.length() - 1);
}
Stack oprStack = new Stack(10);
Stack numStack = new Stack(11);
int index = 0;
String str = "";
while(index < formula.length()) {
char ch = formula.charAt(index);
System.out.println("本次遍历中ch为: " + ch);
if(isOpr(ch)) {// 是运算符
//如果运算符栈中已有运算符,比较添加的运算符与原来的运算符的优先级,新的运算符优先级小于原来的优先级的话,弹出数栈的两个数字,弹出操作符栈的一个运算符,
//进行计算,然后将结果压入数栈,将新的运算符放入操作符栈
if(oprStack.isEmpty()) {
oprStack.push(charToNum(ch));
index++;
continue;
}
while(priority(ch) < priority(numToChar(oprStack.peek()))) {
int num1 = numStack.pop();
int num2 = numStack.pop();
int opr = oprStack.pop();
int result = singleComputer(num1, num2, opr);
numStack.push(result);
}
oprStack.push(charToNum(ch));
index++;
} else {// 不是运算符
// 数字可能是多位数,获取多位数字
while(!isOpr(ch)) {
str += ch;
System.out.println("str值为:" + str);
// 当index指向公式 字符串最后一位时,直接跳出,不在判断下一位是否是数字
if(index >= formula.length() - 1) {
index++;
break;
}
index++;
ch = formula.charAt(index);
}
int num = Integer.parseInt(str);
numStack.push(num);
str = "";
}
}
System.out.println("数栈:");
numStack.printStack();
System.out.println("操作符栈:");
oprStack.printStack();
while(!oprStack.isEmpty()) {
int num1 = numStack.pop();
int num2 = numStack.pop();
int opr = oprStack.pop();
int result = singleComputer(num1, num2, opr);
numStack.push(result);
}
return numStack.pop();
}
/**
* 判断是否是运算符
* @param ch
* @return
*/
public static boolean isOpr(char ch) {
if(ch == '*' || ch == '/' || ch == '+' || ch =='-') {
return true;
}
return false;
}
/**
* 获取运算符的优先级
*/
public static int priority(char ch) {
if(ch == '*' || ch == '/') {
return 1;
}
if(ch == '+' || ch == '-') {
return 0;
}
return -1;
}
/**
* 将运算符转换为数字
*/
public static int charToNum(char opr) {
switch (opr) {
case '+':
return 0;
case '-':
return 1;
case '*':
return 2;
case '/':
return 3;
default:
return -1;
}
}
/**
* 将数字转换为字符
*/
public static char numToChar(int num) {
switch (num) {
case 0:
return '+';
case 1:
return '-';
case 2:
return '*';
case 3:
return '/';
default:
throw new RuntimeException("传入参数错误!");
}
}
/**
* 进行单步运算
*/
public static int singleComputer(int num1, int num2, int opr) {
switch (opr) {
case 0:
return num1 + num2;
case 1:
return num2 - num1;
case 2:
return num1 * num2;
case 3:
return num2 / num1;
default:
throw new RuntimeException("传参错误,单步计算错误");
}
}
}
class Stack {
private int[] stack = null;
private int size;
private int top = -1;
public Stack(int size) {
stack = new int[size];
this.size = size;
}
/**
* 判断栈是否为空
*/
public boolean isEmpty() {
return top == -1;
}
/**
* 判断栈是否满
*/
public boolean isFull() {
return top == size - 1;
}
/**
* 添加操作
*/
public void push(int data) {
if(isFull()) {
System.out.println("栈已满,不能添加新元素");
return;
}
top++;
stack[top] = data;
}
/**
* 弹出栈
*/
public int pop() {
if(isEmpty()) {
throw new RuntimeException("栈为空,无法弹出元素");
}
int val = stack[top];
top--;
return val;
}
/**
* 读取栈顶元素,但不弹出
*/
public int peek() {
if(isEmpty()) {
throw new RuntimeException("栈为空,无法读取栈顶元素");
}
return stack[top];
}
/**
* 打印栈
*/
public void printStack() {
if(isEmpty()) {
System.out.println("栈空间为空");
return;
}
for(int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n", i, stack[i]);
}
}
}
前缀表达式、中缀表达式、后缀表达式
-
前缀表达式
前缀表达式又叫做波兰表达式。前缀表达式是一种没有括号算术的表达式,其将运算符写在前面,将操作数写在后面。
-
中缀表达式
中缀表达式就是常见的运算表达式。
-
后缀表达式
后缀表达式又称逆波兰表达式,与前缀表达式相似,只是运算符位于操作数之后。
表达式的计算
-
前缀表达式
-
从右至左扫描前缀表达式;
-
当扫描到数字,将数字压入到栈中;
-
当扫描到运算符时,从栈弹出两个数字,进行运算,然后将运算结果压入到栈中;
-
继续扫描,重复第二步和第三步,直到栈中仅剩一个数值,该数值为最终结果。
-
-
中缀表达式
- 从左到右扫描中缀表达式;
- 扫描到数字,直接压入数值栈;
- 扫描到左括号,直接压入符号栈;
- 扫描到运算符(+、-、*、/)
- 如果符号栈为空,或者栈顶为“(”,则直接压入符号栈
- 如果是其它情况,则判断运算符的优先级。
- 如果优先级大于栈顶运算符,则直接压入运算符;
- 如果优先级小于等于栈顶运算符,则从数值栈弹出两个元素,从符号栈弹出栈顶运算符,进行运算,然后将运算结果压入数值栈中,重复上一步直至该元素的优先级大于栈顶运算符,或者栈顶元素为左括号,将扫描到的运算符(还未压入符号栈中的运算符)压入符号栈中。
- 扫描到右括号,
- 如果符号栈的栈顶是运算符,则从数值栈中弹出两个数值,从符号栈中弹出一个运算符,进行运算,将结果压入数值栈,重复此步,直至符号栈的栈顶为左括号为止,弹出左括号。
- 如果符号栈的栈顶为左括号,直接弹出左括号即可(一般不会出现这种情况)
- 重复第2~5步,直到扫描完成。
- 如果符号栈不为空,从符号栈弹出一个运算符,从数值栈弹出两个数值进行运算,将结果压入数值栈中,重复此步,直至数值栈中仅剩一个数值,该数值为最终结果。
-
后缀表达式
- 从左到右扫描后缀表达式
- 扫描到数字,将该数字压入栈中。
- 扫描到运算符,从栈中弹出两个数值与该运算符进行运算,将运算结果压入栈中。
- 继续扫描,重复上述第2、3步,直到最终栈中仅剩一个数值,该数值为最终结果。
表达式的转换
-
中缀表达式转换为前缀表达式
1+((2+3)*4)-5
====》- + 1 * + 2 3 4 5
- 从右向左扫描
- 扫描到数字,将其压入结果栈中
- 扫描到运算符(+ 、— 、* 、/)
- 如果符号栈为空或者符号栈栈顶为右括号时,直接压入该运算符
- 如果是其它情况,则对该运算符与栈顶运算符进行比较
- 如果该运算符的优先级大于符号栈的栈顶运算符,则直接压入该运算符
- 如果该运算符的优先级小于等于符号栈的栈顶运算符,这符号栈弹出栈顶运算符,并将弹出的运算符压入结果栈中。重复此步,直至该运算符的优先级大于符号栈的栈顶运算符,或者符号栈的 栈顶元素为右括号,然后将该运算符压入符号栈。
- 扫描到右括号,直接压入符号栈中
- 扫描到左括号,将符号栈中的栈顶弹出,并将弹出元素压入结果栈中,直至符号栈的栈顶元素是右括号,然后弹出右括号。
- 重复以上2~5步,直至扫描完成。
- 如果符号栈依然不为空,将符号栈元素依次弹出放入到结果栈中。
- 最终结果栈全部弹出,弹出为前缀表达式
-
中缀表达式转换为后缀表达式
1+((2+3)*4)-5
====》1 2 3 + 4 * + 5 -
- 从左到右扫描中缀表达式
- 扫描到数字,压入结果栈中
- 扫描到运算符
- 如果符号栈为空或者符号栈栈顶元素为左括号,将运算符直接压入符号栈
- 其它情况,讨论该运算符与符号栈栈顶元素的运算级
- 当该运算符的优先级大于符号栈的栈顶元素,则直接向符号栈中压入该运算符
- 当该运算符的优先级小于等于符号栈的栈顶元素,则弹出符号栈的栈顶元素,并将弹出的元素压入结果栈中。重复此步,直至该运算符的优先级大于符号栈的栈顶元素,或者符号栈的栈顶元素为左括号,向符号栈压入该运算符。
- 扫描到左括号,直接压入符号栈
- 扫描到右括号,弹出符号栈的栈顶元素,将弹出的元素压入到结果栈中,重复此步,直至符号栈的栈顶元素为右括号,然后弹出右括号。
- 继续扫描,重复上述2~5步,直至扫描完成
- 如果符号栈不为空,将符号栈依次弹出,将弹出的元素依次压入结果栈。
- 最终,结果栈全部弹出的倒序为后缀表达式。
部分程序实现
以下程序为中缀表达式转换为后缀表达式,并对后缀表达式求值:
import java.util.ArrayList; import java.util.List; import java.util.Stack; /** * 中缀表达式转换为后缀表达式,并进行计算 * */ public class Test { public static void main(String[] args) { String str = "1+((2+3)*4)-5"; List<String> list = strToList(str); System.out.println(list); List<String> suf = infixToSuffix(list); System.out.println(suf); int res = calculation(suf); System.out.println("结果为:" + res); } /** * 将综合公式字符串转换为ArrayList */ public static List<String> strToList(String str) { if("".equals(str.trim()) || str == null) { throw new RuntimeException("综合表达式输入错误!"); } List<String> list = new ArrayList<>(); for(int i = 0; i < str.length(); i++) { char ch = str.charAt(i); String s = ""; // 根据ASCII, ch为数字 if(ch >= 48 && ch <= 57) { while(ch >= 48 && ch <= 57) { s += ch; //如果是字符串最后一个字符,则不再 i++ if(i == str.length() -1) { break; } i++; ch = str.charAt(i); } list.add(s); // 当因为i为最后一个时,跳出循环,不在i--, if(i != str.length() -1) { i--; } } else { list.add("" + ch); } } return list; } /** * 中缀表达式转换为后缀表达式 */ public static List<String> infixToSuffix(List<String> list) { if(list == null || list.size() == 0) { throw new RuntimeException("参数输入错误!"); } Stack<String> s1 = new Stack<String>(); List<String> s2 = new ArrayList<String>(); for(String str : list) { if(str.matches("\\d+")) { // 判断是数字 s2.add(str); } else if("(".equals(str)) { s1.push(str); } else if(")".equals(str)) { String s = ""; while(true) { s = s1.pop(); if("(".equals(s)) { break; } else { s2.add(s); } } } else {// 是运算符:+ - * / if(s1.isEmpty() || "(".equals(s1.peek())) { s1.push(str); } else if(priority(str) > priority(s1.peek())) { s1.push(str); } else { while(!s1.isEmpty() && !"(".equals(s1.peek())) { s2.add(s1.pop()); } s1.push(str); } } } while(!s1.isEmpty()) { s2.add(s1.pop()); } return s2; } /** * 后缀表达式的计算 */ public static int calculation(List<String> list) { if(list.isEmpty() || list == null) { throw new RuntimeException("传参错误!"); } Stack<Integer> stack = new Stack<>(); for(String str : list) { if(str.matches("\\d+")) { stack.push(Integer.parseInt(str)); } else { int num2 = stack.pop(); int num1 = stack.pop(); if("+".equals(str)) { stack.push(num1 + num2); }else if("-".equals(str)) { stack.push(num1 - num2); }else if("*".equals(str)) { stack.push(num1 * num2); }else if("/".equals(str)) { stack.push(num1 / num2); } } } return stack.pop(); } /** * 判断优先级 */ public static int priority(String str) { if("+".equals(str) || "-".equals(str)) { return 1; } else if("*".equals(str) || "/".equals(str)) { return 2; } else { throw new RuntimeException("参数输入错误!"); } } }
内容总结
以上是互联网集市为您收集整理的数据结构和算法学习日记——栈全部内容,希望文章能够帮你解决数据结构和算法学习日记——栈所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。