数据结构和算法的关系
- 数据结构是一门研究组织数据方式的学科，
- 程序=数据结构+算法
- 数据结构是算法的基础
数据结构结构：
- 线性结构：数组，队列，链表，栈
- 顺序存储结构
- 链式存储结构
- 非线性结构：二维数组，多维数组，广义表，树，图
稀疏数组的概念
当一个数组中大部分元素为0时，或者为同一个值的数组时，可以使用
记录数组一共有几行几列，有多少个不同的数值
把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模
二维数组转为稀疏数组：
- 遍历原始的二维数组，得到有效数据的个数sum
- 根据sum可以创建稀疏数组，三列，sum+1行
- 将二维数组的有效数据存入稀疏数组，第一行存储行列，个数，
稀疏数组转原始二维数组：
- 先读取稀疏数组的第一行，根据第一行的数据，创建二维数组
- 再读取稀疏数组后面行的数组，并赋值给原始二维数组即可
下面是演示如何将一个二维数组转换为稀疏数组
public class SparseArray {
public static void main(String[] args) throws IOException {
//创建一个原始的二维数组11*11
//0：表示没有棋子，1表示黑子，2表示白子
int chessArray1[][] = new int[11][11];
chessArray1[1][2] = 1;
chessArray1[2][3] = 2;
//输出原始的二维数组
System.out.println("原始的二维数组");
for (int[] row:chessArray1) {
for (int data : row) {
System.out.print(data+"\t");
}
System.out.println();
}
//将二维数组压缩为稀疏数组
//先遍历二维数组，得到非0数据的个数
int sum = 0;
for (int i=0;i<11;i++){
for (int j=0;j<11;j++){
if (chessArray1[i][j]!=0){
sum++;
}
}
}
//创建对应的稀疏数组
int sparseArr[][] = new int[sum+1][3];
//给稀疏数组赋值
sparseArr[0][0] = 11;
sparseArr[0][1] = 11;
sparseArr[0][2] = sum;
//以上是给第一行进行赋值,声明原来数组中值的个数和大小
//遍历二维数组，将非0的值存放到稀疏数组中
int count=0;//用于记录是第几个非0数据
for (int i=0;i<11;i++){
for (int j=0;j<11;j++){
if (chessArray1[i][j]!=0){
count++;
sparseArr[count][0] = i;
sparseArr[count][1] = j;
sparseArr[count][2] = chessArray1[i][j];
}
}
}
//输出稀疏数组的形式
System.out.println("得到的稀疏数组为");
for (int[] row:sparseArr) {
for (int data : row) {
System.out.print(data+"\t");
}
System.out.println();
}
//稀疏数组存入文件
File file = new File("C:\\Users\\10505\\Desktop\\arr.txt");
FileWriter fw = new FileWriter(file);
for (int[] row:sparseArr) {
for (int data : row) {
fw.write(data+"\t");
}
fw.write("\r\n");
}
fw.close();
//将稀疏数组恢复为原始的二维数组
//1.先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组
//稀疏数组第一行第一列就是二维数组行数；稀疏数组第一行第二列为二维数组列数
int chessArray2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
for (int index=1;index<sparseArr.length;index++){
chessArray2[sparseArr[index][0]][sparseArr[index][1]] = chessArray2[index][2];
}
//输出恢复后的二维数组
System.out.println("恢复后的二维数组");
for (int[] row:chessArray1) {
for (int data : row) {
System.out.print(data+"\t");
}
System.out.println();
}
//读取文件中的稀疏数组
BufferedReader reader = new BufferedReader(new FileReader(file));
String line ;
int row = 0;
//先定义一个数组来承接读取的数据
int sparseArr2[][] = new int[3][3];
while ((line=reader.readLine())!=null){
String [] temp = line.split("\t");
for (int i = 0; i < temp.length; i++) {
sparseArr2[row][i] = Integer.parseInt(temp[i]);
}
row++;
}
reader.close();
System.out.println("打印从文件中读取的稀疏数组");
for (int[] rows:sparseArr2) {
for (int data : rows) {
System.out.print(data+"\t");
}
System.out.println();
}
}
}
以上就是稀疏数组的压缩和解压缩，原理其实很简单，只是代码写起来有些麻烦，还要文件的写入和写出，就当是顺带复习一下把
队列
先入先出，
这里使用数组模拟队列，创建一个类，类中定义一个数组代表队列，再定义头指针和尾指针，
public class ArrayQueueDemo {
public static void main(String[] args) {
//测试
ArrayQueue queue = new ArrayQueue(3);
char key = ' ';//接收用户输入
Scanner scanner = new Scanner(System.in);
boolean loop = true;
//输出一个菜单
while (loop){
System.out.println("s(show):显示队列");
System.out.println("e(exit):退出程序");
System.out.println("a(add):添加数据到队列");
System.out.println("g(get):从队列取出数据");
System.out.println("h(head):查看队列头数据");
key = scanner.next().charAt(0); //接收一个字符
switch (key){
case 's':
queue.showQueue();
break;
case 'a':
System.out.println("输入一个数字");
int value = scanner.nextInt();
queue.addQueue(value);
break;
case 'g': //取出数据
try {
int res = queue.getQueue();
System.out.println("取出的数据是"+res);
} catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 'h': //查看队列头部数据
try {
int res = queue.headQueue();
System.out.println("取出的头部数据："+res);
} catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 'e': //退出
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出");
}
}
//使用数组模拟队列，编写一个ArrayQueue类
class ArrayQueue{
private int maxSize;//数组的最大容量
private int front; //指向队列头
private int rear; //队列的尾部
private int[] arr; //该数组用于存放数据，模拟队列
//创建队列的构造器
public ArrayQueue (int arrMaxSize){
maxSize = arrMaxSize;
arr = new int[maxSize]; //初始化的时候创建一个数组，这样可以往里面存储数据
front = -1; //初始值头和尾都是-1，指向队列头的前一个位置
rear = -1; //指向队列尾的具体位置，即就是队列最后一个数据的下标
}
//判断队列是否满
public boolean isFull(){
return rear == maxSize - 1;
}
//判断队列是否为空
public boolean isEmpty() {
return rear == front;
}
//添加数据到队列
public void addQueue(int n){
if (isFull()){
System.out.println("队列满,无法加入");
return;
}
rear++; //让rear后移
arr[rear] = n;
}
//数据出队列
public int getQueue(){
//判断队列是否为空
if (isEmpty()){
throw new RuntimeException("队列为空，无法取出数据");
}
front ++; //front往后移，然后将这个下标的元素移出
return arr[front];
}
//显示队列的所有数据
public void showQueue(){
if (isEmpty()) {
System.out.println("队列为空，无数据");
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.println("a["+i+"] = "+arr[i]);
}
}
//显示队列的头数据，
public int headQueue(){
//判断为空
if (isEmpty()) {
throw new RuntimeException("队列为空，没有数据");
}
return arr[front+1];
}
}
但是这个存在一些问题，不是动态的，可能会造成空间的浪费，
接下来对队列进行改造
思路如下：
- 1.front指向队列的第一个元素，
- 2.rear指向对了最后一个元素的后一个值
- 3.队列满的条件 （rear+1）%maxSize = front
- 4.队列判空，rear==front
- 5.队列中的数据的个数 (rear+maxSize-front)%maxSize
- 6.可以在原来的队列上修改
需要把原来的工具类修改一下
//使用数组模拟队列，编写一个ArrayQueue类
class CircleArray {
private int maxSize;//数组的最大容量
private int front; //指向队列头
private int rear; //队列的尾部的后一个值
private int[] arr; //该数组用于存放数据，模拟队列
//创建队列的构造器
public CircleArray(int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int[maxSize]; //初始化的时候创建一个数组，这样可以往里面存储数据
rear = 0;
front = 0;
}
//判断队列是否满
public boolean isFull() {
return (rear + 1) % maxSize == front;
}
//判断队列是否为空
public boolean isEmpty() {
return rear == front;
}
//添加数据到队列
public void addQueue(int n) {
if (isFull()) {
System.out.println("队列满,无法加入");
return;
}
arr[rear] = n;
rear = (rear + 1) % maxSize; //让rear后移,因为有可能循环，所以需要取模
}
//数据出队列
public int getQueue() {
//判断队列是否为空
if (isEmpty()) {
throw new RuntimeException("队列为空，无法取出数据");
}
//这里需要分析出front是指向队列的第一个元素
//先取出保存为临时变量，将front后移，将临时变量返回
int value = arr[front];
front = (front + 1) % maxSize;
return value;
}
//显示队列的所有数据
public void showQueue() {
if (isEmpty()) {
System.out.println("队列为空，无数据");
return;
}
//从front开始遍历，遍历多少个元素
for (int i = front; i <= front + size(); i++) {
System.out.println("a[" + i % maxSize + "] = " + arr[i % maxSize]);
}
}
//求出当前队列有效数据个数
public int size() {
return (rear + maxSize - front) % maxSize;
}
//显示队列的头数据，
public int headQueue() {
//判断为空
if (isEmpty()) {
throw new RuntimeException("队列为空，没有数据");
}
return arr[front];
}
}
好像有些bug，但是我也懒得改了
链表
public class SingleLinkedListDemo {
public static void main(String[] args) {
//先创建节点
HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
//创建一个链表
SingleLinkedList singleLinkedList = new SingleLinkedList();
//加入
// singleLinkedList.add(hero1);
// singleLinkedList.add(hero2);
// singleLinkedList.add(hero3);
// singleLinkedList.add(hero4);
//打乱编号插入
singleLinkedList.addByOrder(hero1);
singleLinkedList.addByOrder(hero3);
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero2);
//显示
singleLinkedList.list();
//测试修改节点的代码
HeroNode newHeroNode = new HeroNode(2,"小王八","麒麟");
singleLinkedList.update(newHeroNode);
//显示
singleLinkedList.list();
//删除一个节点
singleLinkedList.del(1);
singleLinkedList.del(4);
singleLinkedList.del(3);
singleLinkedList.del(3);
System.out.println("删除之后");
singleLinkedList.list();
}
}
//定义SingleLinkedList 管理链表
class SingleLinkedList{
//先初始化一个头节点,头节点不要动,不存放具体的数据
private HeroNode head = new HeroNode(0,"","");
//添加节点到我们的单向链表
public void add (HeroNode heroNode){
HeroNode temp = head;
while (temp.next!=null){
temp = temp.next;
}
temp.next = heroNode;
/*while (true){
if (temp.next == null){
break;
}
//如果没有找到最后，temp后移
temp = temp.next;
}
//退出while循环是，temp指向链表的最后
temp.next = heroNode;*/
}
//第二种方式添加链表元素，将元素插入到指定的位置
public void addByOrder(HeroNode heroNode){
//因为头节点不能动，因此我们仍然通过一个辅助指针来帮助找到添加的位置
//因为是单链表，因此我们找的temp是位于添加位置的前一个节点,否则插入不了
HeroNode temp = head;
boolean flag = false; //标识添加的编号是否存在，默认为false，表示可以插入
while (true) {
if (temp.next == null) {//说明temp已经在链表的最后，
break; //应该要把添加的节点放到末尾了
}
if (temp.next.no > heroNode.no) {
break;
} else if (temp.next.no == heroNode.no){//说明位置已经存在
flag = true; //说明编号存在
break;
}
temp = temp.next;
}
//判断flag的值
if (flag) {//不能添加,编号存在
System.out.println("准备插入的英雄的编号"+heroNode.no+"已经存在了,不能加入 ");
} else {
//插入到链表中
heroNode.next = temp.next;
temp.next = heroNode;
}
}
//修改节点的信息,根据no来修改，即编号不能被修改
public void update(HeroNode heroNode) {
//判断是否为空
if (head.next == null) {
System.out.println("链表为空");
return;
}
//找到需要修改的节点，根据no编号,先定义一个辅助变量
HeroNode temp = head.next;
boolean flag = false;
while (true) {
if (temp == null) {
break; //表示已经遍历完了链表
}
if (temp.no == heroNode.no) {
//找到
flag = true;
break;
}
temp = temp.next;
}
//根据flag判断是否找到需要进行修改的节点
if (flag) {
//temp = heroNode;
temp.name = heroNode.name;
temp.nickName = heroNode.nickName;
} else {
System.out.println("没有找到编号" + heroNode.no + "的节点");
}
}
//删除一个节点
//1.head不能动，因此需要一个temp辅助节点找到待删除节点的前一个节点
//2.说明我们在比较时，是temp.next.no和需要删除的节点的no进行比较
public void del (int no){
HeroNode temp = head;
boolean flag = false; //标识是否找到待删除节点的前一个节点
while (true) {
if (temp.next == null) { //已经到了链表的最后
break;
}
if (temp.next.no == no) {
//找到了待删除节点的前一个节点temp
flag = true;
break;
}
temp = temp.next; //temp后移，遍历
}
if (flag) { //找到
//可以删除
temp.next = temp.next.next;
}else {
System.out.println("需要删除的节点"+no+"不存在");
}
}
//遍历显示链表
public void list(){
//判断链表是否为空
if (head.next == null){
System.out.println("链表为空");
return;
}
//因为头节点不能动，因此我们需要一个辅助变量来遍历
HeroNode temp = head.next;
while (true) {
//判断是否到链表最后
if (temp == null) {
break;
}
//
System.out.println(temp);
temp = temp.next;
}
}
}
//定义一个HeroNode，每个HeroNode对象就是一个节点
class HeroNode{
public int no;
public String name;
public String nickName;
public HeroNode next; //指向下一个节点
//构造器
public HeroNode(int hNo,String name,String nickName){
this.no = hNo;
this.name = name;
this.nickName = nickName;
}
//重写toString方法
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickName='" + nickName + '\'' +
'}';
}
}
具体的就是根据指针进行增删改查
下面是对链表的一些扩展
//获取单链表的节点的个数
public static int getLength(HeroNode head){
if (head.next == null) {
return 0;
}
int length = 0;
//定义一个辅助变量
HeroNode cur = head.next;
while (cur != null) {
length++;
cur = cur.next;
}
return length;
}
查找单链表中的倒数第k个节点[新浪面试题]
//1.编写一个方法，接收head节点，同时接收一个index，表示倒数多少个
//3.先把链表从头到尾遍历，看有多少个节点，然后再计算正向是第几个节点
//4.得到size之后，从链表的第一个开始遍历，遍历size-index，就可以得到
//5.如果找到了，就返回该节点，否则返回null
public static HeroNode findLastIndexNode(HeroNode head,int index){
//判断链表是否为空
if (head.next == null) {
return null;
}
//第一次遍历得到链表的长度(节点个数)
int size = getLength(head);
//第二次，遍历去求解 size-index,就是要求的节点
//先校验
if (index <= 0 || index > size) {
return null;
}
//定义辅助变量
HeroNode cur = head.next;
//从第一个节点开始，移动size-index个节点就是了
for (int i=0;i<size-index;i++){
cur = cur.next;
}
return cur;
}
采用头插法进行单链表反转
public static void reverse(HeroNode head){
//如果当前链表为空或者只有一个节点，就无需反转
if (head.next == null || head.next.next == null) {
return;
}
//这是我自己写的，可以使用
/*HeroNode reverseHead = new HeroNode(0,"","") ;
HeroNode temp ;
while (head.next != null) {
temp = head.next;
head.next = temp.next;
temp.next = reverseHead.next;
reverseHead.next = temp;
}
head.next = reverseHead.next;*/
//定义一个辅助的指针，帮助我们遍历原来的链表
HeroNode cur = head.next;
HeroNode hNext = null; //指向当前节点的下一个节点
HeroNode reverseHead = new HeroNode(0,"","") ;
//遍历原来的链表，并取出节点，头插加入新的链表
while (cur != null) {
hNext = cur.next; //先暂时保留当前节点的下一个节点，因为后面需要使用
cur.next = reverseHead.next;
reverseHead.next = cur;
cur = hNext;
}
head.next = reverseHead.next;
}
接下来将单向链表改造为双向链表
遍历双向链表方法
public void list(){
//判断链表是否为空
if (head.next == null){
System.out.println("链表为空");
return;
}
//因为头节点不能动，因此我们需要一个辅助变量来遍历
HeroNode2 temp = head.next;
while (true) {
//判断是否到链表最后
if (temp == null) {
break;
}
//
System.out.println(temp);
temp = temp.next;
}
}
双向链表添加
public void add (HeroNode2 heroNode){
HeroNode2 temp = head;
while (temp.next!=null){
temp = temp.next;
}
temp.next = heroNode;
heroNode.pre = temp;
/*while (true){
if (temp.next == null){
break;
}
//如果没有找到最后，temp后移
temp = temp.next;
}
//退出while循环是，temp指向链表的最后
temp.next = heroNode;*/
}
修改双向链表一个节点
public void update(HeroNode2 heroNode) {
//判断是否为空
if (head.next == null) {
System.out.println("链表为空");
return;
}
//找到需要修改的节点，根据no编号,先定义一个辅助变量
HeroNode2 temp = head.next;
boolean flag = false;
while (true) {
if (temp == null) {
break; //表示已经遍历完了链表
}
if (temp.no == heroNode.no) {
//找到
flag = true;
break;
}
temp = temp.next;
}
//根据flag判断是否找到需要进行修改的节点
if (flag) {
//temp = heroNode;
temp.name = heroNode.name;
temp.nickName = heroNode.nickName;
} else {
System.out.println("没有找到编号" + heroNode.no + "的节点");
}
}
双向链表中删除一个节点
public void del (int no){
if (head.next == null) {
System.out.println("链表为空，不能删除");
return;
}
HeroNode2 temp = head.next;
boolean flag = false; //标识是否找到待删除节点
while (true) {
if (temp == null) { //已经到了链表的最后节点的next
break;
}
if (temp.no == no) {
//找到了待删除节点的前一个节点temp
flag = true;
break;
}
temp = temp.next;
}
if (flag) { //找到
//可以删除
temp.pre.next = temp.next;
//如果是最后一个节点，就不需要执行下面的语句，否则会空指针
if (temp.next != null){
temp.next.pre = temp.pre;
}
}else {
System.out.println("需要删除的节点"+no+"不存在");
}
}
按照顺序往里面插入节点
public void addByOrder(HeroNode2 heroNode){
if (head.next == null) {
head.next = heroNode;
heroNode.pre = head;
}
HeroNode2 temp = head.next;
while (temp != null) {
if (temp.no > heroNode.no) {
heroNode.pre = temp.pre;
temp.pre.next = heroNode;
heroNode.next = temp;
temp.pre = heroNode;
break;
}
temp = temp.next;
}
}
约瑟夫问题
约瑟夫需要创建一个单向的循环链表这样更加容易解决问题，
class CircleLinkedList{
private Boy first = null;
//添加小孩节点，构建成一个环形链表
public void addBoy(int nums){
//nums做校验
if (nums < 1) {
System.out.println("nums的值不正确");
return;
}
Boy cur = null; //辅助变量，帮助构建环形链表
//使用for循环来创建我们的环形链表
for (int i = 1; i <= nums; i++) {
//根据编号,创建小孩节点
Boy boy = new Boy(i);
if (i == 1) {
first = boy;
first.next = first; //构成一个环状
cur = first;
} else {
cur.next = boy;
boy.next = first;
cur = cur.next;
}
}
}
//遍历当前环形链表
public void showBoy(){
//判断链表是否为空
if (first == null) {
System.out.println("链表为空");
return;
}
//因为first不能动,定义一个辅助指针，完成遍历
Boy cur = first;
while (true) {
System.out.println("小孩的编号"+cur.no);
if (cur.next == first) {
System.out.println("遍历完毕");
break;
}
cur = cur.next;
}
}
}
然后求解的时候也有些复杂，
根据用户的输入，看有多少个小孩，然后计算出小孩出去的顺序
- 需要创建一个辅助的指针，因为我们刚开始的时候是从第一个孩子数起，所以使用辅助指针
- 辅助指针最开始指向头节点的前一个，
- 我们每查两次都会删除一个，意思就是辅助指针的next。next节点被删除
- 我们需要一个指针去往前走两步找到需要删除的节点，但是节点删除之后这个指针指向的位置就很尴尬
- 所以我们每次都靠辅助指针来决定起始位置
- 当小孩报数时，让first和helper同时移动m-1次，
- 这时将first指向的节点进行删除，
- 具体操作：first节点向前移动，辅助节点的next = first即可 ，
- 这样被删除的节点就没有任何引用了，然后就会被jvm垃圾回收
- 辅助指针向后移动一个，这样它还是会指向下次开始节点的前一个节点
/**
* 根据用户的输入，计算出出圈的顺序
* @param startNo 表示从第几个小孩开始数
* @param countNum 表示数几次删除一个
* @param nums 表示最初有多少小孩在圈中
*/
public void countBoy(int startNo,int countNum,int nums){
//对数据进行校验
if (first == null || startNo < 1 || startNo > nums) {
System.out.println("数据输入有误");
return;
}
//先创建一个辅助指针,帮助完成小孩出圈
Boy helper = first;
//让helper指向环形队列的最后节点
while (helper.next != first) {//helper指向最后的节点
helper = helper.next;
}
//小孩报数前，先让first和helper移动到指定的节点
for (int j=0;j<startNo-1;j++){
first = first.next;
helper = helper.next;
}
//当小孩报数时，让first和helper指针同时移动m-1次，然后出圈
//这时一个循环的操作，直到圈中只有一个节点
while (true){
if (helper == first){ //这时说明权中只有一个节点了
break;
}
//让first和helper同时移动countNum-1次，然后出圈
for (int j=0;j<countNum-1;j++){
first = first.next;
helper = helper.next;
}
//这时first指向要出圈的小孩节点
System.out.println(first.no+"小孩出圈");
first = first.next;
helper.next = first;
}
System.out.println("最后留在圈中的小孩"+first.no);
}
栈
- 先入后出
- 变化的一端为栈顶，不变的一端为栈底
- 出栈pop，入栈push
栈的应用场景：
- 子程序调用
- 递归调用
- 表达式转换
- 二叉树遍历
- 图的深度优化
使用数组来模拟栈
class ArrayStack{
private int maxSize; //栈的容量
private int[] stack; //数组，数组模拟栈，数据就放在该数组
private int top = -1; //top表示栈顶，初始化为-1
//构造器
public ArrayStack(int maxSize){
this.maxSize = maxSize;
stack = new int[maxSize];
}
//栈满
public boolean isFull(){
return top >= maxSize-1;
}
//栈空
public boolean isEmpty(){
return top == -1;
}
//入栈
public void push(int value){
//先判断栈是否满
if (isFull()) {
System.out.println("栈满");
return;
}
top++;
stack[top] = value;
}
//出栈,将栈顶的数据返回
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("第"+i+"个数据"+stack[i]);
}
}
}
使用栈来完成算术表达式的思想
- 通过一个index索引来遍历我们的表达式，
- 如果我们发现是数字，就直接进入数栈
- 如果是符号，分为如下的情况
- dan当发现符号栈为空，z直接入栈，
- 符号栈有操作符，就进行比较，如果当前d的操作符的优先级小于等于栈中的操作符就从数栈中pop出两个数，再从符号栈中pop出一个符号，然后进行运算，然后再把运算结构push入数栈，把新的符号push入符号栈
- 如果符号栈有符号，但是当前符号的优先级大于栈中的符号，那么久把当前符号进栈
public class Calculator {
public static void main(String[] args) {
//根据前面的思路，完成表达式的解析运算
String expression = "170+2*6-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 = ""; //用于拼接多位数
//开始循坏的扫描expression，
while (true) {
//依次得到每一个expression的字符
ch = expression.substring(index,index+1).charAt(0);
//判断ch是什么
if (operStack.isOper(ch)){//如果是一个运算符
//判断当前的符号栈是否为空
if (!operStack.isEmpty()){
//如果符号栈有操作符，就进行比较，
if (operStack.priority(ch)<=operStack.priority(operStack.peek())){
// 如果当前的操作符的优先级小于等于栈中操作符 pop两个数
num1 = numStack.pop();
num2 = numStack.pop();
//符号栈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 {//如果是数，直接入数栈
//numStack.push(ch-48); //因为ASIC码和实际的数字不太对应，有些偏差
//分析，当我们处理多位数时，不能发现一个数就立即入栈，
//因为这可能是多位数,
//所以我们在处理数的时候，需要向expression的表达式的index后再看一位，
//因此我们需要定义一个变量 字符串，用于拼接，
//处理多位数
keepNum += ch;
//如果ch已经是expression的最后一位，直接入栈
if (index == expression.length()-1){
numStack.push(Integer.parseInt(keepNum));
}else {
//判断下一个字符是不是数字,如果是数字，继续扫描，如果是运算符，则入栈
//只是往后看一位
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;
}
}
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出来
System.out.println("表达式"+expression+"= "+numStack.pop());
}
}
这也太繁琐了
![Java String.format方法的简单使用[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)