目录
单向环形链表
Josephu(约瑟夫、约瑟夫环)问题
提示
示意图
构建一个单向的环形链表思路
遍历环形链表
约瑟夫问题分析图解和实现(1)
完整代码
约瑟夫问题分析图解和实现(2)
完整代码
栈的应用场景和介绍
栈的介绍
出栈(pop)和入栈(push)的概念
栈的应用场景
数组模拟栈的思路分析图
实现栈的思路分析
完整代码
运行结果
栈实现综合计算器
思路分析(1)
代码实现(2)
完整代码
运行结果
代码实现(3)
完整代码
前缀、中缀、后缀表达式
前缀表达式(波兰表达式)
中缀表达式
后缀表达式
后缀表达式的计算机求值
逆波兰计算器分析和实现
完整代码
中缀转后缀思路分析
思路步骤分析
代码实现
单向环形链表
Josephu(约瑟夫、约瑟夫环)问题
Josephu问题为：设编号为1，2，...n的n个人围坐一圈，约定编号为k(1<=k<=n)的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，以此类推，直到所有人出列为止，由此产生一个出列编号的序列。
提示
用一个不带头结点的循环链表来处理Josephu问题:先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，记到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。
示意图
n=5,即有5个人
k=1,从第一个人开始报数————>单向环形链表完成，约瑟夫问题
m=2,数2下
构建一个单向的环形链表思路
1.先创建第一个节点，让first指向该节点，并形成环形
2.后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可
遍历环形链表
1.先让一个辅助指针(变量)curBoy,指向first节点
2.然后通过一个while循环遍历该该环形链表即可curBoy.next==first结束
约瑟夫问题分析图解和实现(1)
完整代码
package linkedlist;
public class Josepfu {
public static void main(String[] args) {
//测试一把看看环形链表，和遍历是否ok
CircleSinglelinkedList circleSinglelinkedList=new CircleSinglelinkedList();
circleSinglelinkedList.addBoy(5);//加入5个小孩节点
circleSinglelinkedList.showBoy();
}
}
//创建一个环形的单向链表
class CircleSinglelinkedList{
//创建一个first节点，当前没有编号
private Boy first=null;
//添加小孩节点，构建成一个环形的链表
public void addBoy(int nums) {
//nums做一个数据校验
if (nums<1) {
System.out.println("nums的值不正确");
return;
}
Boy curBoy=null;//辅助指针，帮助构建环形链表
//使用for来创建我们的环形链表
for (int i = 0; i <=nums; i++) {
//根据编号，创建小孩节点
Boy boy=new Boy(i);
//如果是第一个小孩
if (i==1) {
first=boy;
first.setNext(first);//构成环
curBoy=first;//让curBoy指向第一个小孩
}else {
curBoy.setNext(boy);
boy.setNext(first);
curBoy=boy;
}
}
}
//遍历当前的环形链表
public void showBoy() {
//判断链表是否为空
if (first==null) {
System.out.println("没有任何小孩~~");
return;
}
//因为first不能动，因此我们仍然使用一个辅助指针完成遍历
Boy curBoy=first;
while (true) {
System.out.printf("小孩的编号%dn",curBoy.getNo());
if (curBoy.getNext()==first) {//说明已经遍历完毕
break;
}
curBoy=curBoy.getNext();//curBoy后移
}
}
}
//创建一个Boy类，表示一个节点
class Boy{
private int no;//编号
private Boy next;//指向下一个节点，默认null
public Boy(int no) {
this.no=no;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public Boy getNext() {
return next;
}
public void setNext(Boy next) {
this.next = next;
}
}
约瑟夫问题分析图解和实现(2)
package linkedlist;
public class Josepfu {
public static void main(String[] args) {
//测试一把看看环形链表，和遍历是否ok
CircleSinglelinkedList circleSinglelinkedList=new CircleSinglelinkedList();
circleSinglelinkedList.addBoy(5);//加入5个小孩节点
circleSinglelinkedList.showBoy();
}
}
//创建一个环形的单向链表
class CircleSinglelinkedList{
//创建一个first节点，当前没有编号
private Boy first=null;
//添加小孩节点，构建成一个环形的链表
public void addBoy(int nums) {
//nums做一个数据校验
if (nums<1) {
System.out.println("nums的值不正确");
return;
}
Boy curBoy=null;//辅助指针，帮助构建环形链表
//使用for来创建我们的环形链表
for (int i = 0; i <=nums; i++) {
//根据编号，创建小孩节点
Boy boy=new Boy(i);
//如果是第一个小孩
if (i==1) {
first=boy;
first.setNext(first);//构成环
curBoy=first;//让curBoy指向第一个小孩
}else {
curBoy.setNext(boy);
boy.setNext(first);
curBoy=boy;
}
}
}
//遍历当前的环形链表
public void showBoy() {
//判断链表是否为空
if (first==null) {
System.out.println("没有任何小孩~~");
return;
}
//因为first不能动，因此我们仍然使用一个辅助指针完成遍历
Boy curBoy=first;
while (true) {
System.out.printf("小孩的编号%dn",curBoy.getNo());
if (curBoy.getNext()==first) {//说明已经遍历完毕
break;
}
curBoy=curBoy.getNext();//curBoy后移
}
}
}
//创建一个Boy类，表示一个节点
class Boy{
private int no;//编号
private Boy next;//指向下一个节点，默认null
public Boy(int no) {
this.no=no;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public Boy getNext() {
return next;
}
public void setNext(Boy next) {
this.next = next;
}
}
约瑟夫问题分析图解和实现(2)
根据用户的输入，生成一个小孩出圈的顺序
1.需求创建一个辅助指针(变量)helper,事先应该指向环形链表的最后这个节点
补充：小孩报数前，先让first和helper移动k-1次
2.当小孩报数前，让first和helper指针同时的移动m-1次
3.这时就可以将first指向的小孩节点出圈
first=first.next;
helper.next=first
原来first指向的节点就没有任何引用，就会被回收
出圈的顺序:2——>4——>1——>5——>3
//根据用户的输入，计算出小孩出圈的顺序
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 (true) {
if (helper.getNext()==first) {//说明helper指向最后小孩节点
break;
}
helper=helper.getNext();
}
//小孩报数前，先让first和helper移动k-1次
for (int j = 0; j < startNo-1; j++) {
first=first.getNext();
helper=helper.getNext();
}
//小孩报数时，先让first和helper指针同时移动k-1次,然后出圈
//这里是一个循环操作，知道圈中只有一个节点
while (true) {
if (helper==first) {//说明圈中只有一个节点
break;
}
//让first和helper指针同时的移动countNum-1,然后出圈
for (int j = 0; j
完整代码
package linkedlist;
public class Josepfu {
public static void main(String[] args) {
//测试一把看看环形链表，和遍历是否ok
CircleSinglelinkedList circleSinglelinkedList=new CircleSinglelinkedList();
circleSinglelinkedList.addBoy(5);//加入5个小孩节点
circleSinglelinkedList.showBoy();
//测试一把小孩出圈是否正确
circleSinglelinkedList.countBoy(10, 20, 125);
}
}
//创建一个环形的单向链表
class CircleSinglelinkedList{
//创建一个first节点，当前没有编号
private Boy first=null;
//添加小孩节点，构建成一个环形的链表
public void addBoy(int nums) {
//nums做一个数据校验
if (nums<1) {
System.out.println("nums的值不正确");
return;
}
Boy curBoy=null;//辅助指针，帮助构建环形链表
//使用for来创建我们的环形链表
for (int i = 0; i <=nums; i++) {
//根据编号，创建小孩节点
Boy boy=new Boy(i);
//如果是第一个小孩
if (i==1) {
first=boy;
first.setNext(first);//构成环
curBoy=first;//让curBoy指向第一个小孩
}else {
curBoy.setNext(boy);
boy.setNext(first);
curBoy=boy;
}
}
}
//遍历当前的环形链表
public void showBoy() {
//判断链表是否为空
if (first==null) {
System.out.println("没有任何小孩~~");
return;
}
//因为first不能动，因此我们仍然使用一个辅助指针完成遍历
Boy curBoy=first;
while (true) {
System.out.printf("小孩的编号%dn",curBoy.getNo());
if (curBoy.getNext()==first) {//说明已经遍历完毕
break;
}
curBoy=curBoy.getNext();//curBoy后移
}
}
//根据用户的输入，计算出小孩出圈的顺序
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 (true) {
if (helper.getNext()==first) {//说明helper指向最后小孩节点
break;
}
helper=helper.getNext();
}
//小孩报数前，先让first和helper移动k-1次
for (int j = 0; j < startNo-1; j++) {
first=first.getNext();
helper=helper.getNext();
}
//小孩报数时，先让first和helper指针同时移动k-1次,然后出圈
//这里是一个循环操作，知道圈中只有一个节点
while (true) {
if (helper==first) {//说明圈中只有一个节点
break;
}
//让first和helper指针同时的移动countNum-1,然后出圈
for (int j = 0; j
栈的应用场景和介绍
栈的介绍
1)栈的英文为stack
2)栈是一个先入后出的有序列表
3)栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top),另一端为固定的一端，称为栈底。
4)根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好想反，最后放入的元素最先删除，最先放入的元素最后删除。
出栈(pop)和入栈(push)的概念
栈的应用场景
1)子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
2)处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
3）表达式的转换[中缀表达式转后缀表达式]与求值（实际解决）
4）二叉树的遍历
5）图形的深度优先(depth-first)搜索法
数组模拟栈的思路分析图
实现栈的思路分析
1.使用数组来模拟栈
2.定义一个top来表示栈顶，初始化为-1
3.入栈的操作，当有数据加入到栈时，top++;stack[top]=data
4.出栈的操作，int value=stack[top];top--;return value
完整代码
package stack;
import java.util.Scanner;
public class ArrayStackDemo {
public static void main(String[] args) {
//测试一下ArrayStack是否正确
//先创建一个ArrayStack对象->表示栈
ArrayStack stack=new ArrayStack(4);
String key="";
boolean loop=true;//控制是否退出菜单
Scanner scanner=new Scanner(System.in);
while (loop) {
System.out.println("show:表示显示栈");
System.out.println("exit:退出程序");
System.out.println("push:表示添加数据到栈(入栈)");
System.out.println("pop:表示从栈取出数据(出栈)");
System.out.println("请输入你的选择");
key=scanner.next();
switch (key) {
case "show":
stack.list();
break;
case "push":
System.out.println("请输入一个数");
int value=scanner.nextInt();
stack.push(value);
break;
case "pop":
try {
int res=stack.pop();
System.out.printf("出栈的数据是%d",res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case "exit":
scanner.close();
loop=false;
break;
default:
break;
}
}
System.out.println("程序退出~~");
}
}
//定义一个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;
}
//入栈
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]=%dn",i,stack[i]);
}
}
}
运行结果
栈实现综合计算器
思路分析(1)
使用栈完成表达式的计算思路
1.通过一个index值(索引)，来遍历我们的表达式
2.如果我们发现是一个数字，就直接入数栈
3.如果发现扫描到是一个符号，就分如下情况
3.1 如果发现当前的符号栈为空，就直接入栈
3.2如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或着等于栈中的操作符，就需要从数栈中pop出两个数，在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈。
4.当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运行。
5.最后在数栈只有一个数字，就是表达式的结果
验证:3+2*6-2=13
代码实现(2)
完整代码
package stack;
public class Calculator {
public static void main(String[] args) {
//根据前面老师的思路，完成表达式的运算
String expression="3+2*6-2";
//创建两个栈，数栈，一个符号栈
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
//开始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 {//如果是数，则直接入数栈
numStack.push(ch-48);
}
//让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;
}
//入栈
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]=%dn",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=num1/num2;
break;
default:
break;
}
return res;
}
}
运行结果
代码实现(3)
String keepNum=" ";//用于拼接多位数
//numStack.push(ch-48);
//分析思路
//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))) {
//如果后一位是运算符，则入栈keepNum="1"或者"123"
numStack.push(Integer.parseInt(keepNum));
//重要的!!!,keepNum清空
keepNum=" ";
}
}
完整代码
package stack;
public class Calculator {
public static void main(String[] args) {
//根据前面老师的思路，完成表达式的运算
String expression="7*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 {//如果是数，则直接入数栈
//numStack.push(ch-48);
//分析思路
//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))) {
//如果后一位是运算符，则入栈keepNum="1"或者"123"
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;
}
//入栈
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]=%dn",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=num1/num2;
break;
default:
break;
}
return res;
}
}
前缀、中缀、后缀表达式
前缀表达式(波兰表达式)
从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算(栈顶元素和次顶元素)，并将结果入栈：重复上述过程知道表达式最左端，最后运算出的值即为表达式的结果。
中缀表达式
1)中缀表达式就是常见的运算表达式，如(3+4)*5-6
2）中缀表达式的求值是我们人最熟悉的，但是对计算机来说却不好操作（前面我们讲的案例就能看到这个问题),因此。在计算结果时，往往会将中缀表达式转成其他表达式来操作(一般转成后缀表达式)
后缀表达式
1)后缀表达式又称逆波兰表达式与前缀表达式相似，只是运算符位于操作符以后
2)中举例说明:(3+4)*5-6对应的后缀表达式就是34+5*6-
后缀表达式的计算机求值
从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算(次顶元素和栈顶元素)，并将结果入栈:重复上述过程直到表达式最右端，最后运算得出得值即为表达式的结果。
逆波兰计算器分析和实现
完整代码
package stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class PolandNotation {
public static void main(String[] args) {
//先定义给逆波兰表达式
//(3+4)*5-6=>3 4+5*6-
//说明为了方便，逆波兰表达式的数字和符号使用空格隔开
String suffixexpression="3 4+5*6-";
//思路
//1.先将"3 4+5*6-"=>放到ArrayList
//2.将ArrayList传递给一个方法，遍历ArrayList配合栈完成计算
List list=getListString(suffixexpression);
System.out.println("rpnList"+list);
int res=calculate(list);
System.out.println("计算的结果是="+res);
}
//将一个逆波兰表达式，依次将数据和运算符放入到ArrayList中
public static ListgetListString(String suffixexpression){
//将suffixexpression分割
String[] split=suffixexpression.split("");
List list=new ArrayList();
for (String ele:split) {
list.add(ele);
}
return list;
}
//完成对逆波兰表达式的运算
public static int calculate(Listls) {
//创建给栈，只需要一个栈即可
Stack stack=new Stack();
//遍历ls
for (String item:ls) {
//这里使用正则表达式来取出数
if (item.matches("\d+")) {//匹配的是多位数
//入栈
stack.push(item);
}else {
//pop出两个数，并运算，再入栈
int num2=Integer.parseInt(stack.pop());
int num1=Integer.parseInt(stack.pop());
int res=0;
if (item.equals("+")) {
res=num1+num2;
}else if (item.equals("-")) {
res=num1-num2;
}else if (item.equals("*")) {
res=num1*num2;
}else if (item.equals("/")) {
res=num1/num2;
}else {
throw new RuntimeException("运算有误");
}
//把res入栈
stack.push(""+res);
}
}
//最后留在stack中的数据是运算结果
return Integer.parseInt(stack.pop());
}
}
中缀转后缀思路分析
思路步骤分析
代码实现
package stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class PolandNotation {
public static void main(String[] args) {
//完成将一个中缀表达式转成后缀表达式得到功能
//说明
//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.将得到的中缀表达式对应的List=>后缀表达式对应的List
String expression="1+((2+3)*4)-5";
ListinfixexpressionList=toInfixexpressionList(expression);
System.out.println("中缀表达式对应的List"+infixexpressionList);
List suffixexpressionList=parseSuffixexpressionList(infixexpressionList);
System.out.println("后缀表达式对应的List"+suffixexpressionList);
System.out.printf("expression",calculate(suffixexpressionList));
//先定义给逆波兰表达式
//(3+4)*5-6=>3 4+5*6-
//说明为了方便，逆波兰表达式的数字和符号使用空格隔开
String suffixexpression="30 4+5*6-";
//思路
//1.先将"3 4+5*6-"=>放到ArrayList
//2.将ArrayList传递给一个方法，遍历ArrayList配合栈完成计算
List list=getListString(suffixexpression);
System.out.println("rpnList"+list);
int res=calculate(list);
System.out.println("计算的结果是="+res);
}
//即ArrayList[1,+,(,2,+,3,),*,4,),-,5]=>ArrayList[1,2,3,4,*,+,5,-]
//方法:将中缀表达式转化成对应的List
public static ListparseSuffixexpressionList(List ls){
//定义两个栈
Stack s1=new Stack();//符号栈
//说明:因为s2这个栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出
//因此比较麻烦，这里我们就不用Stack直接使用Lists2
//Stack s2=new Stack();//储存中间结果的栈s2
Lists2=new ArrayList();//储存中间结果的List s2
//遍历ls
for (String item:ls) {
//如果是一个数，加入s2
if (item.matches("\d+")) {
s2.add(item);
}else if (item.equals("(")) {
s1.push(item);
}else if (item.equals("")) {
//如果是右括号")",则依次弹出s1栈顶的运算符，并压入s2，直到
//遇到左括号为止，此时将这一对括号丢弃
while (!s1.peek().equals("(")) {
s2.add(s1.pop());
}
s1.pop();//!!!将（弹出s1栈，消除小括号
}else {
//当item的优先级小于等于s1栈顶运算符，
//将s1栈顶的运算符弹出并加入到s2中，再次转到(4.1)与s1中的栈顶运算符相比较
//问题:我们确少一个比较优先级高低的方法
while (s1.size()!=0&&Operation.getValue(s1.peek())>=Operation.getValue(item)){
s2.add(s1.pop());
}
//还需要将item压入栈
s1.push(item);
}
}
//将s1中剩余的运算符依次弹出并加入s2
while (s1.size()!=0) {
s2.add(s1.pop());
}
return s2;//注意因为是存放到List，因此按顺序输出就是对应的后缀表达式
}
public static List toInfixexpressionList(String s){
//定义一个List,存放中缀表达式对应的内容
List ls=new ArrayList();
int i=0;//这时是一个指针，用于遍历中缀表达式字符串
String str;//对多位数的拼接
char c;//每遍历到一个字符，就放入到c
do {
//如果c是一个非数字，我需要加入到ls
if ((c=s.charAt(i))<48||(c=s.charAt(i))>57) {
ls.add(""+c);
i++;//i需要后移
}else {//如果是一个数，需要考虑多位数
str="";//先将str置成""
while (i=48&&(c=s.charAt(i))<=57) {
str+=c;//拼接
i++;
}
ls.add(str);
}
}while(igetListString(String suffixexpression){
//将suffixexpression分割
String[] split=suffixexpression.split("");
List list=new ArrayList();
for (String ele:split) {
list.add(ele);
}
return list;
}
//完成对逆波兰表达式的运算
public static int calculate(Listls) {
//创建给栈，只需要一个栈即可
Stack stack=new Stack();
//遍历ls
for (String item:ls) {
//这里使用正则表达式来取出数
if (item.matches("\d+")) {//匹配的是多位数
//入栈
stack.push(item);
}else {
//pop出两个数，并运算，再入栈
int num2=Integer.parseInt(stack.pop());
int num1=Integer.parseInt(stack.pop());
int res=0;
if (item.equals("+")) {
res=num1+num2;
}else if (item.equals("-")) {
res=num1-num2;
}else if (item.equals("*")) {
res=num1*num2;
}else if (item.equals("/")) {
res=num1/num2;
}else {
throw new RuntimeException("运算有误");
}
//把res入栈
stack.push(""+res);
}
}
//最后留在stack中的数据是运算结果
return Integer.parseInt(stack.pop());
}
}
//编写一个类Operation可以返回一个运算符 对应的优先级
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 "/":
result=DIV;
break;
default:
System.out.println("不存在该运算");
}
return result;
}
}
