java链栈的表达式求值--多位数以及小数求值
MyStack.java的代码:
package page1.p5.p51;
public class MyStack
{
public class Node<T>
{
public T data;
public Node next;
}
public class Stack<T>
{
private Node bottom; //栈底指针
private Node top; //栈顶指针
private Integer size; //栈当前大小
public void initStack()
{
bottom = top = new Node();
top.next = bottom;
size = 0;
}
public boolean isEmpty()
{
if (top.next == bottom)
{
return true;
}
return false;
}
public void pushStack(T element)
{
Node temp = new Node();
temp.data = element;
if (top.next == bottom)//第一次入栈操作
{
temp.next = bottom;
top.next = temp;
}
else
{
temp.next = top.next;
top.next = temp;
}
size++;
}
public T popStack()
{
Node temp = new Node();
T t=null;
if (isEmpty())
{
System.out.println("栈中没有元素！");
}
else
{
temp=top.next;
t= (T) temp.data;
//System.out.println("出栈操作：" + top.next.data + " ");
top.next = top.next.next;
temp=null;
}
size--;
return t;
}
public int sizeStack()
{
return size;
}
public T getTop()
{
//System.out.println("顶部值：" + top.next.data);
return (T) top.next.data;
}
public void printStack()
{
Node temp = top;
if (isEmpty())
{
System.out.println("栈中没有元素！");
}
else
{
for (int i = 0; i < size; i++)
{
System.out.print(temp.next.data + " ");
temp = temp.next;
}
}
System.out.println();
}
}
}
DoMain代码:
package page1.p5.p51;
import java.math.BigDecimal;
public class DoMain
{
static char [] a1={'+','-','*','/','(',')','^','#'};
static char a2 [][]={
{'>','>','<','<','<','>','<','>'},
{'>','>','<','<','<','>','<','>'},
{'>','>','>','>','<','>','<','>'},
{'>','>','>','>','<','>','<','>'},
{'<','<','<','<','<','=','<',' '},
{'>','>','>','>',' ','>','>','>'},
{'>','>','>','>','<','>',' ','>'},
{'<','<','<','<','<',' ','<','='}
};
static int GetIndex(char data)
{
switch(data) {
case '+': return 0;
case '-': return 1;
case '*': return 2;
case '/': return 3;
case '(': return 4;
case ')': return 5;
case '^': return 6;
case '#': return 7;
}
return -1;
}
static char Precede(char data1,char data2)
{
return a2[GetIndex(data1)][GetIndex(data2)];
}
static double Operate(BigDecimal a,char ch,BigDecimal b)
{
BigDecimal temp;
if(ch=='+')
{
return a.add(b).doubleValue();
}
else if(ch=='-')
{
return a.subtract(b).doubleValue();
}
else if(ch=='*')
{
return a.multiply(b).doubleValue();
}
else if(ch=='/')
{
return a.divide(b).doubleValue();
}
else
{
return Math.pow(a.doubleValue(),b.doubleValue());
}
}
static double NumberHandle(int num1,int num2)
{
return Math.pow(num1,num2);
}
static void StrHandle(StringBuffer str)
{
int i,len=str.length();
for(i=1;i<len;i++)
{
if(str.charAt(i)=='-'&&i==1)
{
str.insert(i,'0' );
//len++;
}
if((str.charAt(i)=='-')&&(str.charAt(i-1)=='('||str.charAt(i-1)=='^'))
{
str.insert(i,'0' );
//len++;
}
if(str.charAt(i)=='.')
{
if(i==1)
{
str.insert(i,'0' );
//len++;
}
else
{
if(str.charAt(i-1)=='+'||str.charAt(i-1)=='-'||str.charAt(i-1)=='*'||
str.charAt(i-1)=='/'||str.charAt(i-1)=='^'||str.charAt(i-1)=='(')
{
str.insert(i,'0' );
//len++;
}
}
}
}
}
static double ExpressValue(StringBuffer str,MyStack.Stack<Character> characterStack,
MyStack.Stack<Double> doubleStack)
{
characterStack.initStack();
doubleStack.initStack();
int i=1,len=0,point=0;
double num = 0,num1=0,num2=0;
char ch=0,sch=0;
BigDecimal b1=null,b2=null;
StrHandle(str);
len=str.length();
characterStack.pushStack(str.charAt(0));
while(i<len)
{
if(str.charAt(i)>='0'&&str.charAt(i)<='9')
{
num = num*10 + (double)((int)str.charAt(i)-(int)'0');
i++;
}
else if(str.charAt(i)=='.')
{
point=i;
i++;
}
else
{
/*
1.运算符前面的数字不为0，数值进栈
2.运算符，即'-'与后面的数字构成负数，'-'前面的0进栈
*/
if((num!=0)||(num==0&&str.charAt(i-1)=='0'))
{
if(point!=0)
{
num=num/NumberHandle(10,i-point-1);
doubleStack.pushStack(num);
num=0;
point=0;
}
else
{
doubleStack.pushStack(num);
num=0;
}
}
sch=Precede(characterStack.getTop(),str.charAt(i));
switch(sch)
{
case '<':
characterStack.pushStack(str.charAt(i));
i++;
break;
case '>':
ch=characterStack.popStack();
num2=doubleStack.popStack();
num1=doubleStack.popStack();
b1=new BigDecimal(num1+"");
b2=new BigDecimal(num2+"");
doubleStack.pushStack(Operate(b1,ch,b2));
break;
case '=':
ch=characterStack.popStack();
i++;
break;
}
}
}
return doubleStack.getTop();
}
public static void main(String[] args)
{
/*MyStack.Stack<Character> characterStack=new MyStack().new Stack<>();
char ch = 0;
characterStack.initStack();
characterStack.pushStack('1');
characterStack.pushStack('2');
characterStack.pushStack('3');
ch=characterStack.popStack();
System.out.println(ch);*/
MyStack.Stack<Character> characterStack=new MyStack().new Stack<>();
MyStack.Stack<Double> doubleStack=new MyStack().new Stack<>();
//StringBuffer str=new StringBuffer("#-.5+.7#");
StringBuffer str=new StringBuffer("#10*(1*(2+6/3)-1)+3^(3-1)+1+1-2#");
System.out.println(ExpressValue(str,characterStack,doubleStack));
}
}
可以将DoMain.java中的静态方法封装成一个工具类，使代码更简洁。我懒得封装了，有点java基础的都可以轻松实现。
实现原理和我之前c++实现的原理一样，只是换了一种编程语言。
