【数据结构】利用栈实现表达式求值

短命女 2021-09-16 11:29 482阅读 0赞

## 前言 ##

java实现，利用int类型存储操作数，完善了char类型范围太小的问题，利用递归，完善了括号嵌套使用的问题。

## 运行结果截图 ##

![在这里插入图片描述][70]

代码实现：

import java.util.Arrays; import java.util.Scanner; public class StackTest{ //测试 public static void main(String[] args) throws Exception { ArrayStack OPTR = new ArrayStack(); ArrayStack OPND = new ArrayStack(); EvaluateExpressions ee = new EvaluateExpressions(); ee.EvaluateExpression(OPTR,OPND); int sum = (int)OPND.GetTop(); System.out.println("表达式的结果为："+sum); } } class ArrayStack<T> { //栈的相关方法 private int max_size;//栈的容量 private T[] array;//栈数组 private int top;//栈顶指针 public ArrayStack(){ //申请内存空间 this.max_size=100; array = (T[])new Object[max_size]; this.top=-1; } public ArrayStack(int size){ this.max_size=size; array = (T[])new Object[max_size]; this.top=-1; } public void Push(T t){ //入栈 top++; if (top>array.length-1){ T[] copy = Arrays.copyOf(array,max_size*2); array=copy; } array[top]=t; } public T Pop() throws Exception{ //出栈 if(top>=0){ return array[top--]; }else{ throw new Exception("空栈，无法进行出栈操作"); } } public T GetTop() throws Exception{ //获得栈顶元素 if(top<0) throw new Exception("空栈，栈顶为空"); else return array[top]; } public boolean isEmpty(){ //栈的判空 if(top==-1) return true; else return false; } } class EvaluateExpressions{ //运算的相关方法 private static String expression;//表达式 private static int index=0;//表达式的第 index 个位置 private static char c; //表达式第index个位置上的对应的字符 static { //静态代码块，从键盘读取计算表达式 Scanner in = new Scanner(System.in); System.out.println("请输入表达式："); expression = in.next(); expression+="#"; //在表达式结尾加入#，以免输入的时候忘记输入 c=expression.charAt(index); } public boolean isDight(char c){ //判断字符是否是数字 if(c>='0'&&c<='9') return true; else return false; } public int swap_char_into_int(char c){ //将字符转换为相应的数字，用来判断优先级 switch(c){ case '+':return 0; case '-':return 1; case '*':return 2; case '/':return 3; case '(':return 4; case ')':return 5; case '#':return 6; default: return -1; } } public char Predece(char a,char b){ //将优先级按照对应的顺序存入一个二维数组，根据两个符号的坐标位置得到优先级 int i,j; int flag; int[][] symbol={ { 0,0,1,1,1,0,0}, { 0,0,1,1,1,0,0}, { 0,0,0,0,1,0,0}, { 0,0,0,0,1,0,0}, { 1,1,1,1,1,2,4}, { 0,0,0,0,4,0,0}, { 1,1,1,1,1,4,2}, }; i=swap_char_into_int(a); j=swap_char_into_int(b); flag=symbol[i][j]; switch(flag){ case 0:return '>'; case 1:return '<'; case 2:return '='; default: return '4'; //说明表达式出错 } } public int Operate(int a,char x,int b){ //根据数字和符号计算并返回结果 int sum=0; switch(x){ case '+':{ sum=a+b;break;} case '-':{ sum=a-b;break;} case '*':{ sum=a*b;break;} case '/':{ sum=a/b;break;} } return sum; } public int EvaluateExpression(ArrayStack OPTR,ArrayStack OPND ) throws Exception { /* * 运用了递归的思想，分别计算每个括号里的内容 * * */ OPTR.Push('#'); int num=0;//存放从表达式中读取倒是数字 char x; //存放从表达式中读取到的运算符 int flag=0;//flag=0 说明上一个字符不是数字，flag=1 说明上一个字符为数字 while(c!='#'||(char)OPTR.GetTop()!='#'){ if(c=='(') { /* * 遇到左括号，开始递归 * 新建两个栈，一个寄存运算符，一个寄存数字（运算结果） * */ c=expression.charAt(++index);//读取括号的下一位 int sum = EvaluateExpression(new ArrayStack(),new ArrayStack());//递归 OPND.Push(sum);//将计算结果压入数字栈 } if (c==')'&&(char)OPTR.GetTop()=='#') { //如果读取又括号，并且运算符栈为空，说明该括号内容计算完毕 c = expression.charAt(++index);//读取下一个字符 return (int) OPND.GetTop();//返回结果 } if(isDight(c)==true){ //如果该字符是数字 if(flag==0){ //如果一个字符不是数字 num = (int)(c-'0'); //char转int OPND.Push(num);//入栈 flag=1; c = expression.charAt(++index);; }else{ //如果上一个字符是数字 num = (int)OPND.GetTop(); //获得数字栈 的栈顶元素 num =num*10+(int)(c-'0'); //将 这个数字拼接在一起 OPND.Pop(); //删除栈顶元素 OPND.Push(num);//重新入栈 flag=1; c = expression.charAt(++index);; } }else { flag=0; switch (Predece((char)OPTR.GetTop(),c)){ case '<': //栈顶元素优先级低 { OPTR.Push(c);c = expression.charAt(++index);;break;} case '=': //脱掉括号 { OPTR.Pop();c = expression.charAt(++index);break;} case '>'://栈顶元素优先级高 { x=(char)OPTR.Pop();int b=(int)OPND.Pop();int a=(int)OPND.Pop(); OPND.Push(Operate(a,x,b));break; } } } } return (int)OPND.GetTop(); } }

[70]: /images/20210724/05d262791c83402a900ada95a40c481c.png