数据结构之栈(前、中、后缀表达式)
本文共 12055 字，大约阅读时间需要 40 分钟。
1 栈的介绍
1)栈的英文是stack2)栈是一个先进后出的有序列表3)栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表,允许插入和删除的一段,为变化的一段,称为栈顶(top),另一端为固定的一端,称为栈底(bottom)
2 栈的应用场景
1)子程序的调用:在跳往子程序前,会先将下一指令的地址存到堆栈中,直到子程序执行完后再将地址取出,以回到原来的程序中.2)处理递归调用:和子程序的调用类似,只是除了储存下一个指令的地址外,也将参数,区域变量等数据存入栈中.3)表达式的转换[中缀表达式转后缀表达式]与求值4)二叉树的遍历5)图形的深度优先(depth-first)搜索法
3 实现栈的思路
package com.dataStructure.com.dataStructure.stack;import java.util.Scanner;public class StackDemo { public static void main(String[] args) { Arraystack stack = new Arraystack(2); 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.showList(); break; case "push": System.out.println("请输入一个数"); int value = scanner.nextInt(); stack.push(value); break; case "pop": try { int pop = stack.pop(); System.out.println(pop); }catch (Exception e){ System.out.println(e.getMessage()); } break; case "exit": scanner.close(); loop = false; break; } } System.out.println("程序结束"); }}class Arraystack{ private int top = -1; //top的初始位置 private int[] stack; //定义一个数组 private int maxSize; public Arraystack(int maxSize){ this.maxSize = maxSize; stack = new int[this.maxSize]; } //是否为空 public boolean isEmpty(){ return top == -1; } //是否满 public boolean isFull(){ return top == maxSize - 1; } //入栈操作 public void push(int value){ if(isFull()){ System.out.println("stack is full,can not push"); return; } top ++; stack[top] = value; } //出栈操作 public int pop(){ if(isEmpty()){ throw new RuntimeException("stack is empty"); } int value = stack[top]; top --; return value; } //显示栈的情况 public void showList(){ if(isEmpty()){ System.out.println("stack is empty"); return; } for (int i = top; i >=0 ; i--) { System.out.printf("stack[%d]=%d\n",i,stack[i]); } }} 4 用栈实现计算机计算器功能
思路分析:
1)通过一个index值(索引),来遍历我们的表达式 2)如果我们发现是一个数字,就直接入数栈 3)如果发现扫描到是一个符号,就分如下情况 3.1:如果发现当前的符号为空,就直接入栈 3.2:如果符号栈有操作符,就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符,就需要从数栈中pop出两个数,在从符号栈中pop出一个符号,进行运算,将得到结果,入数栈,然后将当前的操作符入符号栈,如果当前的操作符的优先级大于栈的操作符,就直接入符号栈 4)当前表达式扫描完毕,就顺序的从数栈和符号栈中pop出相应的数和符号,并运行. 5)最后在数栈只有一个数字,就是表达式的结果package com.dataStructure.com.dataStructure.stack;public class Caculator { public static void main(String[] args) { String expression = "30+2*6-2"; ArrayStack01 numStack = new ArrayStack01(10); ArrayStack01 operStack = new ArrayStack01(10); int index = 0; int num01 = 0; int num02 = 0; int oper = 0; int result = 0; char ch = ' '; //将每次扫描得到的char保存到ch String keepNum = ""; //用于处理多位数的 while (true){ ch = expression.substring(index, index + 1).charAt(0); if (operStack.isOper(ch)){ if(operStack.isEmpty()){ operStack.push(ch); }else{ if(operStack.priority(ch) <= operStack.priority(operStack.peek())){ num01 = numStack.pop(); num02 = numStack.pop(); oper =operStack.pop(); result = numStack.cal(num01,num02,oper); numStack.push(result); operStack.push(ch); }else { operStack.push(ch); } } }else{ //numStack.push(ch - 48); keepNum += ch; 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 = ""; } } } index ++; if(index >= expression.length()){ break; } } while (true){ if(operStack.isEmpty()){ break; } num01 = numStack.pop(); num02 = numStack.pop(); oper = operStack.pop(); result = numStack.cal(num01,num02,oper); numStack.push(result); } int res = numStack.pop(); System.out.printf("表达式%s = %d",expression,res); }}class ArrayStack01{ private int top = -1; private int[] stack; private int maxSize; public ArrayStack01(int maxSize){ this.maxSize = maxSize; stack = new int[maxSize]; } public boolean isEmpty(){ return top == -1; } public boolean isFull(){ return top == maxSize - 1; } //增加一个方法,返回当前的栈顶值,但不是真正的出栈 public int peek(){ return stack[top]; } public void push(int value){ if(isFull()){ System.out.println("stack id full,can not push"); } top ++; stack[top] = value; } public int pop(){ if(isEmpty()){ throw new RuntimeException("stack is empty"); } int value = stack[top]; top --; return value; } public void showStack(){ if(isEmpty()){ System.out.println("stack is empty"); 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 num01,int num02,int oper){ int result = 0; switch (oper){ case '+': result = num01 +num02; break; case '-': result = num02 - num01; break; case '*': result = num01 * num02; break; case '/': result = num02 / num01; break; } return result; }} 5 前缀、中缀、后缀表达式(逆波兰表达式)
(1)前缀表达式：前缀表达式又称波兰式,前缀表达式的运算符位于操作数之前
计算机求值 从右至左扫描时,遇到数字时,将数字压入栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做响应的计算,并将结果入栈,重复上述过程直到表大四最左端,最后运算得到的值即为表达式的结果.
(3)后缀表达式:又称逆波兰表达式,运算符位于操作数之后
计算机求值从左至右扫描表达式,遇到数字时,将数字压入栈中,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算,并将结果入栈,重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果.
package com.dataStructure.com.dataStructure.stack;import java.util.ArrayList;import java.util.List;import java.util.Stack;public class PolandNotation { public static void main(String[] args) { String e = "3 4 + 5 * 6 -"; List list = getListString(e); System.out.println(list); int caculate = caculate(list); System.out.println(caculate); } public static List getListString(String expression){ String[] split = expression.split(" "); ArrayList list = new ArrayList<>(); for (String s : split) { list.add(s); } return list; } public static int caculate(List ls){ Stack stack = new Stack<>(); for (String item : ls) { if(item.matches("\\d+")){ stack.push(item); }else{ int num01 = Integer.parseInt(stack.pop()); int num02 = Integer.parseInt(stack.pop()); int result = 0; if(item.equals("+")){ result = num01 + num02; }else if(item.equals("-")){ result = num02 - num01; }else if(item.equals("*")){ result = num01 * num02; }else if(item.equals("/")){ result = num02 /num01; }else{ throw new RuntimeException("运算符有误"); } stack.push(""+result); } } return Integer.parseInt(stack.pop()); }} 中缀表达式转后缀表达式
思路分析:
1)初始化两个栈,运算符栈s1和存储中间结果的栈s2 2)从做至右扫描中缀表达式 3)遇到操作数时,将其压s2 4)遇到运算符时,比较其与s1栈顶运算符的优先级(括号不算运算符) 4.1如果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中的元素并输出,结果的逆序即是中缀表达式转逆缀表达式的结果.
代码实现 ```public class PolandNotation {public static void main(String[] args) { String s = "1+((2+3)*4)-5"; List list = infixExpressionToList(s); System.out.println(list); System.out.println("=================="); List list1 = parseSuffixExpressionList(list); System.out.println(list1); int caculate = caculate(list1); System.out.println(caculate);}//将中缀表达式对应list -> 后缀表达式public static List parseSuffixExpressionList(List list) { Stack s1 = new Stack<>(); ArrayList s2 = new ArrayList<>(); //为了简便,在这里s2,我们不用栈,用list for (String item : list) { if (item.matches("\\d+")) { s2.add(item); } else if (item.equals("(")) { s1.push(item); } else if (item.equals(")")) { while (!s1.peek().equals("(")) { s2.add(s1.pop()); } s1.pop(); //消除小括号 } else { while (s1.size() != 0 && Operation.getValue(item) <= Operation.getValue(s1.peek())) { s2.add(s1.pop()); } s1.push(item); } } //将s1剩余的运算符一次弹出并加入s2 while (s1.size() != 0) { s2.add(s1.pop()); } return s2;}//将中缀表达式转换为listpublic static List infixExpressionToList(String expression) { ArrayList list = new ArrayList<>(); int i = 0; //字符串的指针 String str; //对多位数的拼接 char c; //每遍历一个字符 放入C do { if ((c = expression.charAt(i)) < '0' || (c = expression.charAt(i)) > '9') { list.add("" + c); i++; } else { str = ""; while (i < expression.length() && (c = expression.charAt(i)) >= '0' && (c = expression.charAt(i)) <= '9') { str += c; i++; } list.add(str); } } while (i < expression.length()); return list;}public static List getListString(String expression) { String[] split = expression.split(" "); ArrayList list = new ArrayList<>(); for (String s : split) { list.add(s); } return list;}public static int caculate(List ls) { Stack stack = new Stack<>(); for (String item : ls) { if (item.matches("\\d+")) { stack.push(item); } else { int num01 = Integer.parseInt(stack.pop()); int num02 = Integer.parseInt(stack.pop()); int result = 0; if (item.equals("+")) { result = num01 + num02; } else if (item.equals("-")) { result = num02 - num01; } else if (item.equals("*")) { result = num01 * num02; } else if (item.equals("/")) { result = num02 / num01; } else { throw new RuntimeException("运算符有误"); } stack.push("" + result); } } return Integer.parseInt(stack.pop()); }}``````class Operation {private static int ADD = 1;private static int SUB = 1;private static int MUL = 1;private static int DIV = 1;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; }}``` 转载地址：http://cjmzi.baihongyu.com/
你可能感兴趣的文章