X16数据结构部分03
栈实现综合计算器思路
/*
栈实现综合计算器
栈计算表达式的结果
思路分析
有两个栈：数栈 符号栈
数栈专门存放数字的 符号栈存放运算符
通过一个索引index遍历表达式
如果扫描到的是一个数字，直接入数栈
如果扫描到的是一个符号，则分以下两种情况
当前符号栈为空，直接入栈
当前符号栈不为空，又分两种情况
当前操作符<=栈顶操作符，数栈pop出两个数，
符号栈pop出一个符号，进行运算，将得到的结果入数栈
当前操作符入符号栈
当前操作符>栈顶操作符，直接入符号栈
表达式扫描完毕，就顺序地从符号栈和数栈中pop出数字和符号，并运算
最后数栈中的栈底，就是结果
之后你就可以照此思路验证3 + 6 * 2 - 2
*/
栈实现综合计算器代码实现
package dc;
/**
* @author 404小恐龙
* @version 1.8
* @date 2021/10/7 11:09
*/
public class d18 {
public static void main(String[] args) {
/*
初始化数据
中缀表达式和两个栈
*/
String expression = "13+2*6-2";
ArrayStack numberStack = new ArrayStack(10);
ArrayStack operatorStack = new ArrayStack(10);
/*
定义需要的相关变量
用于扫描的索引
每次扫描得到的char保存到ch里面
用于拼接多位数的字符串变量
*/
int index = 0,num1 = 0,num2 = 0,operator = 0,result = 0;
char ch = ' ';
String keepNum = "";
/*
开始循环字符串表达式
*/
while(index < expression.length()){
/*
取出字符串相应位置的值
并转为字符
这一步很nice
*/
ch = expression.substring(index,index+1).charAt(0);
/*
判断ch是什么字符
*/
if (operatorStack.isOperator(ch)){
/*
程序运行到这里
说明是操作符
接下来分情况入栈
*/
if (!operatorStack.isEmpty()){
/*
程序运行到这里
说明符号栈不为空
再接着进行优先级判断
*/
if (operatorStack.priority(ch) <= operatorStack.priority(operatorStack.peek())){
num1 = numberStack.pop();
num2 = numberStack.pop();
operator = operatorStack.pop();
result = numberStack.calculate(num1,num2,operator);
/*
运算结果入数栈
再把当前运算符入栈
*/
numberStack.push(result);
operatorStack.push(ch);
}else{
/*
程序运行到此处
说明当前优先级大于符号栈栈顶的优先级
直接入栈
*/
operatorStack.push(ch);
}
}else{
/*
程序运行到此处
说明符号栈为空
直接入栈
*/
operatorStack.push(ch);
}
}else{
/*
todo
程序运行到此处
说明传进来的是一个数字
这里注意
这时入栈的是字符1
对应的ASCII数字为49
所以需要减去48
这个地方出现了问题
由于栈是一次入栈一个字符
多位数运算容易出现问题
所以在处理expression表达式时
应该向后面再看一位
如果是数就继续扫描
不能马上入栈
而且在向后看的时候
还需要做一层判断
看是否是最后一位
否则会报java.lang.StringIndexOutOfBoundsException
所以我们应该定义一个字符串变量用于拼接
*/
keepNum += ch;
if (index == expression.length() - 1){
numberStack.push(Integer.parseInt(keepNum));
}else{
if (operatorStack.isOperator(expression.substring(index+1,index+2).charAt(0))){
/*
程序运行到此处
说明后一位是操作符
此时可以入栈
入栈完后需要清空
*/
numberStack.push(Integer.parseInt(keepNum));
keepNum = "";
}
// numberStack.push(ch - 48);
}
}
/*
程序运行到此处
说明对该字符处理已经完成
while循环会判断是否扫描完
没扫描完的话
继续扫描下一个
*/
index++;
}
/*
程序运行到此处
说明第一轮的字符串处理已经结束
接下来进行有序的弹栈运算
最后数栈剩下一个数就是结果
*/
while (!operatorStack.isEmpty()){
num1 = numberStack.pop();
num2 = numberStack.pop();
operator = operatorStack.pop();
result = numberStack.calculate(num1,num2,operator);
numberStack.push(result);
}
System.out.println(numberStack.pop());
}
}
/*
栈类
*/
class ArrayStack{
private int maxSize; //栈的大小
private int[] stack; //数组模拟栈 数据放在数组中
private int top = -1; //top 表示栈顶
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new int[maxSize];
}
/**
* 返回栈顶元素
* @return 栈顶元素
*/
public int peek(){
return stack[top];
}
/**
* 判断栈满
* @return 是否已经满了
*/
public boolean isFull(){
return top == maxSize - 1;
}
/**
* 判断栈空
* @return 是否已经空了
*/
public boolean isEmpty(){
return top == -1;
}
/**
* 入栈
* @param value 入栈的元素
*/
public void push(int value){
//先判断栈是否满
if(isFull()){
System.out.println("栈满");
return;
}
top ++;
stack[top] = value;
}
/**
* 出栈
* @return 弹出的元素
*/
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]);
}
}
/**
* 扩展功能
* 优先级判断
* 优先级高低由程序员决定
* 优先级由数字表示
* 数字越大优先级越高
* @param operator 运算符
* @return 优先级
*/
public int priority(int operator){
/*
这里要注意使用单引号
假定运算中只有加减乘除
*/
if (operator == '*' || operator == '/'){
return 1;
}else if (operator == '+' || operator == '-'){
return 0;
}else{
/*
程序能走到这一步
说明传入的参数有问题
*/
return -1;
}
}
/**
* 判断是否为运算符
* @param operator 传入的符号
* @return 是否为运算符 返回true 表示是
*/
public boolean isOperator(int operator){
return operator == '+' || operator == '-' || operator == '*' || operator == '/';
}
/**
* 计算方法
* @param num1 参与计算的数字
* @param num2 参与计算的数字
* @param operator 参与计算的操作符
* @return 计算的结果
*/
public int calculate(int num1,int num2,int operator){
int result = 0; // 用于存放计算的结果
switch (operator){
/*
这里注意运算顺序
栈是后进先出的
所以减法和除法需要做一下顺序调整
*/
case '+':
result = num1 + num2;
break;
case '-':
result = num2 - num1;
break;
case '*':
result = num1 * num2;
break;
case '/':
result = num2 / num1;
break;
default:
break;
}
return result;
}
}
广义表的逻辑结构和存储结构
/*
广义表
线性表中的元素不可再分
就是一个广义表
A = () 空表 长度为0 深度为1
B = (b,d) B的元素全是原子，b和d，长度为2，深度为1
C = (b,(c,d)) 长度为2，深度为2
D = (B,C) 长度为2，深度为3
E = (a,E) 长度为2，无限深度
当广义表非空时
第一个元素为表头
其余元素为表尾
例如取B的表头和表尾
d加括号的原因
是一个构建广义表的操作
把表头元素取出来
其余元素构建一个新的广义表
所以需要加括号
GetHead(B) = b;
GetTail(B) = (d);
再例如取原子a的表头和表尾
GetHead((a)) = (a);
GetTail((a)) = ();
*/
/*
广义表的存储结构
B->[1 p[0 b] next]->[1 p[0 d] ^]
0 代表原子节点
1 代表广义表节点
有2个结构体
3个域和2个域
3个域的第2个是一个指针
指向存原子的域
C->[1 p1 next]->[1 p2 ^]
p1->[0 b]
p2->[1 p3 next]->[1 p4 ^]
p3->[0 c]
p4->[0 d]
*/
前缀中缀后缀表达式规则
/*
关于栈的3种表达式
前缀中缀后缀
其中后缀表达式又叫做逆波兰表达式
例如中缀表达式 (3+4)*5-6 对应的后缀表达式 34+5*6-
首先从左向右扫描
3，4依次入栈
然后遇上+操作符
弹出栈顶和次顶元素4，3，计算得7，入栈
5入栈，遇见操作符*，弹出顶部和次顶元素5，7，计算得35，入栈
6入栈，遇见操作符-，弹出顶部和次顶元素35，6，计算得29
注意：后缀表达式减法操作符是后面弹出来的减去前面弹出来的
其中前缀表达式又叫做波兰表达式
运算符位于操作数之前
例如中缀表达式 (3+4)*5-6 对应的前缀表达式 -*+3456
首先从后先前扫描，6543依次入栈
扫描到运算符+，弹出栈顶和次顶元素3，4
得到7，将7入栈
接下来是*操作符，弹出7和5，得35入栈
最后是-操作符，弹出35和6，得29
注意：减法运算符规则是先弹出的元素减去后弹出的元素
中缀表达式存在，为什么要提供前缀和后缀表达式呢
因为中缀表达式对人来说很好理解
但对于计算机来说不是这个样子
真正的计算一般会把中缀表达式转为后缀表达式再做计算
*/
逆波兰计算器实现
package dc;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* @author 404小恐龙
* @version 1.8
* @date 2021/10/8 15:04
*/
public class d19 {
/*
需求：逆波兰计算器实现
也就是后缀表达式
*/
public static void main(String[] args) {
/*
定义逆波兰表达式
为了方便
数字和操作符之间
使用空格隔开
*/
String reversePolishNotation = "3 4 + 5 * 6 -";
List<String> strings = expressionToArray(reversePolishNotation);
System.out.println(strings); // [3, 4, +, 5, *, 6, -]
int i = reversePolishNotationCal(strings);
System.out.println(i); // 29
}
/**
* 表达式转数组方法
* @param expression 表达式字符串
* @return 表达式数组
*/
public static List<String> expressionToArray(String expression){
/*
分割字符串
*/
String[] split = expression.split(" ");
List<String> arrayList = new ArrayList<>();
for (String s : split) {
arrayList.add(s);
}
return arrayList;
}
/**
* 完成逆波兰表达式的计算
* @param list 表达式数组
* @return 结果
*/
public static int reversePolishNotationCal(List<String> list){
/*
创建一个栈
*/
Stack<String> stack = new Stack<>();
for (String s : list) {
if (s.matches("\\d+")){
/*
程序运行到此处
说明匹配的是数字
并且有可能是多位数
直接入栈即可
*/
stack.push(s);
}else{
/*
程序运行到此处
说明扫描到操作符
从栈中pop出两个数并运算
注意需要调换位置
*/
int num2 = Integer.parseInt(stack.pop());
int num1 = Integer.parseInt(stack.pop());
int result = 0;
if (s.equals("+")){
result = num1 + num2;
}else if (s.equals("-")){
result = num1 - num2;
}else if (s.equals("*")){
result = num1 * num2;
}else if (s.equals("/")){
result = num1 / num2;
}else{
throw new RuntimeException("operator wrong");
}
/*
程序运行到此处
说明操作符处理完毕
将得到的结果入栈
注意需要将整数转字符串
否则与栈的泛型冲突
*/
stack.push(result + "");
}
}
return Integer.parseInt(stack.pop());
}
}