建立中英文网站,东莞市招标网,太原网站建设搜q479185700,蓝杉互动网站建设文章目录 1. 关于栈的一个实际应用2. 栈的介绍3. 栈的应用场景4. 栈的简单应用4.1. 思路分析4.2. 代码实现 5. 栈的进阶应用(实现综合计算器)5.1. 栈实现一位数计算(中缀表达式)5.1.1. 思路分析5.1.2. 代码实现 5.2. 栈实现多位数计算(中缀表达式)5.2.1. 解决思路5.2.2. 代码实… 文章目录 1. 关于栈的一个实际应用2. 栈的介绍3. 栈的应用场景4. 栈的简单应用4.1. 思路分析4.2. 代码实现 5. 栈的进阶应用(实现综合计算器)5.1. 栈实现一位数计算(中缀表达式)5.1.1. 思路分析5.1.2. 代码实现 5.2. 栈实现多位数计算(中缀表达式)5.2.1. 解决思路5.2.2. 代码实现 1. 关于栈的一个实际应用
设计一个简单的计算器 输入一个表达式点击计算得出结果。 如计算式:[7 * 2 * 2 - 5 1 - 5 3 - 3] 点击计算【如下图】 请问: 计算机底层是如何运算得到结果的 注意不是简单的把算式列出运算, 而是计算机怎么理解这个算式的(对计算机而言它接收到的就是一个字符串)我们讨论的是这个问题。– 栈
2. 栈的介绍
栈(stack)是一个先入后出(FILO-First In Last Out)的有序列表。栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端为变化的一端称为栈顶(Top)另一端为固定的一端称为栈底(Bottom)。根据栈的定义可知最先放入栈中元素在栈底最后放入的元素在栈顶而删除元素刚好相反最后放入的元素最先删除最先放入的元素最后删除
图解方式说明出栈(pop)和入栈(push)的概念 3. 栈的应用场景
子程序的调用在跳往子程序前会先将下个指令的地址存到堆栈中直到子程序执行完后再将地址取出以回到原来的程序中。处理递归调用和子程序的调用类似只是除了储存下一个指令的地址外也将参数、区域变量等数据存入堆栈中。表达式的转换[中缀表达式 转 后缀表达式]与求值(实际解决)。二叉树的遍历。图形的深度优先(depth 一 first)搜索法。
4. 栈的简单应用
问题 用数组模拟栈的使用由于栈是一种有序列表当然可以使用数组的结构来储存栈的数据内容下面我们就用数组模拟栈的出栈入栈等操作。
4.1. 思路分析
思路分析(使用数组来模拟栈) ①定义一个 top 来表示栈顶初始化 为 -1 ②入栈的操作当有数据加入到栈时 top; stack[top] data; ③出栈的操作 int value stack[top]; top--, return value
4.2. 代码实现
package stack;import java.util.Scanner;public class ArrayStackDemo {public static void main(String[] args) {// 创建一个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\n, res);} catch (Exception e) {// TODO: handle exceptionSystem.out.println(e.getMessage());}break;case exit:scanner.close();loop false;break;default:break;}}System.out.println(程序退出);}
}// 定义一个ArrayStck 表示栈
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.printf(stack[%d]%d\n, i, stack[i]);}}}运行结果 习题拓展 将上面的程序改成使用链表来模拟栈。 5. 栈的进阶应用(实现综合计算器)
5.1. 栈实现一位数计算(中缀表达式)
使用栈来实现综合计算器 问题 请输入一个表达式通过点击“点击计算”来输出计算结果 计算的表达式为7 * 2 * 2 - 5 1 - 5 3 - 3 5.1.1. 思路分析
假设 计算表达式为3 2 * 6 - 2
计算思路
1.通过一个 index 值索引来遍历我们的表达式
2.如果我们发现是一个数字, 就直接入数栈 3.如果发现扫描到是一个符号, 就分如下情况
3.1. 如果发现当前的符号栈为 空就直接入栈 3.2. 如果符号栈有操作符就进行比较 1如果当前的操作符的优先级小于或者等于栈中的操作符 就需要从数栈中pop出两个数,在从符号栈中pop出一个符号进行运算将得到结果入数栈然后将当前的操作符入符号栈 2如果当前的操作符的优先级大于栈中的操作符 就直接入符号栈。 因为计算表达式为3 2 * 6 - 2 栈中已经存放了3和下一步该想数栈中存放2直接入栈 接下来扫描到符号 * 当前的操作符 * 的优先级大于栈中的操作符 直接入符号栈 接下来扫描到数字6直接入数栈 接下来扫描到符号 - 当前的操作符 - 的优先级小于(或等于)栈中的操作符 * 直接入符号栈 需要从数栈中pop出两个数6 和 2,在从符号栈中pop出一个符号*进行运算将得到结果12入数栈 2 * 6 12 然后将当前的操作符 - 入符号栈。 接下来扫描到数字2直接入数栈 4.当表达式扫描完毕就顺序的从 数栈和符号栈中pop出相应的数和符号并运行
①12 - 2 10 ②3 10 13 5.最后在数栈只有一个数字就是表达式的结果即13
5.1.2. 代码实现
package stack;public class Calculator {public static void main(String[] args) {// 给出一个计算表达式String expression 32*6-2;// String expression 72*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// 使用while循环的扫描expressionwhile (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);// ASCII码表对应数值要减去48}// 让index并判断是否扫描到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);}
}// 先创建一个栈
// 定义一个ArrayStck 表示栈
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];}// 增加一个方法可以返回当前栈顶的值但不是真正的poppublic 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;// 用于存放计算结果switch (oper) {case :res num2 num1;break;case -:res num2 - num1;break;case *:res num2 * num1;break;case /:res num2 / num1;break;default:break;}return res;}}运行结果 注意 上述代码在计算多位数会出现问题比如计算302*6-2会错误的计算成10 因为在数据读取的时候是一个字符一个字符的读取这样就把30拆成了 3 和 0 因此计算出错。 5.2. 栈实现多位数计算(中缀表达式)
5.2.1. 解决思路
1.当处理多位数时不能发现是一个数就立即入栈因为它可能是多位数 2.在处理数时需要向expression的表达式的index后再看一位如果是多位数就进行扫描如果是符号才入栈 3.因此我们需要定义一个变量 字符串用于拼接
5.2.2. 代码实现
package stack;public class Calculator {public static void main(String[] args) {// 给出一个计算表达式String expression 302*6-2;// String expression 72*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保存到chString keepNum ;//用于拼接多位数// 使用while循环的扫描expressionwhile (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);// ASCII码表对应数值要减去48//分析思路//1. 当处理多位数时不能发现是一个数就立即入栈因为它可能是多位数//2.在处理数时需要向expression的表达式的index后再看一位如果是多位数就进行扫描如果是符号才入栈//3.因此我们需要定义一个变量 字符串用于拼接//处理多位数keepNum ch;//如果ch已经是expression的最后一位就直接入栈if (index expression.length() - 1) {numStack.push(Integer.parseInt(keepNum));} else {// 判断下一个字符是不是数字如果是数字就继续扫描如果是运算符则入栈// 注意这里是看后一位不是indexif (operStack.isOper(expression.substring(index 1, index 2).charAt(0))) {// 如果后一位是运算符则入栈(keepNum可能是 一位数也可能是 多位数)numStack.push(Integer.parseInt(keepNum));// 注意一定要清空keepNumkeepNum ;}}}// 让index并判断是否扫描到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);}
}// 先创建一个栈
// 定义一个ArrayStck 表示栈
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];}// 增加一个方法可以返回当前栈顶的值但不是真正的poppublic 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;// 用于存放计算结果switch (oper) {case :res num2 num1;break;case -:res num2 - num1;break;case *:res num2 * num1;break;case /:res num2 / num1;break;default:break;}return res;}}运行结果 习题拓展
对上述代码加入功能能够实现含小括号表达式的运算。
