package cal.reverse;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
/**
* 逆波兰算法 （计算器的应用）
* @author HP
*
*
一、 将中缀表达式转换成后缀表达式算法：
1、从左至右扫描一中缀表达式。
2、若读取的是操作数，则判断该操作数的类型，并将该操作数存入操作数堆栈
3、若读取的是运算符
(1) 该运算符为左括号"("，则直接存入运算符堆栈。
(2) 该运算符为右括号")"，则输出运算符堆栈中的运算符到操作数堆栈，直到遇到左括号为止。
(3) 该运算符为非括号运算符：
(a) 若运算符堆栈栈顶的运算符为括号，则直接存入运算符堆栈。
(b) 若比运算符堆栈栈顶的运算符优先级高或相等，则直接存入运算符堆栈。
(c) 若比运算符堆栈栈顶的运算符优先级低，则输出栈顶运算符到操作数堆栈，并将当前运算符压入运算符堆栈。
4、当表达式读取完成后运算符堆栈中尚有运算符时，则依序取出运算符到操作数堆栈，直到运算符堆栈为空。
二、逆波兰表达式求值算法：
1、循环扫描语法单元的项目。
2、如果扫描的项目是操作数，则将其压入操作数堆栈，并扫描下一个项目。
3、如果扫描的项目是一个二元运算符，则对栈的顶上两个操作数执行该运算。
4、如果扫描的项目是一个一元运算符，则对栈的最顶上操作数执行该运算。
5、将运算结果重新压入堆栈。
6、重复步骤2-5，堆栈中即为结果值。
*/
public class ReverseCal {
//类级内部类相当于其外部类的成员，只有在第一次被使用的时候才会被装载
private static class ReverseCalHolder{
//静态初始化器，由JVM来保证线程安全
private static ReverseCal instance=new ReverseCal();
}
private ReverseCal(){};
public static ReverseCal getInstace()
{
return ReverseCalHolder.instance;
}
/**
* 将中缀表达式转化为 逆波兰表达式
* @param exp
* @return
*/
public String reverseExp(String exp)
{
int length=exp.length();
Stack<String> valStack = new Stack<String>();
Stack<String> opStack = new Stack<String>();
String val=null;
Operation.OPRATION op=null;
for(int inx=0;inx<length;inx++)
{
val=exp.substring(inx,inx+1);
op=Operation.getInstance().getOp(exp.charAt(inx));
switch(op)
{
case LEFT:
{
opStack.push(val);
break;
}
case RIGHT:
{
while ((!opStack.isEmpty()) && (!opStack.peek().equals("(")))
{
valStack.push(opStack.pop());
}
if((!opStack.isEmpty()) && opStack.peek().equals("("));
opStack.pop();
break;
}
case OTHER:
{
valStack.push(val);
break;
}
//+-*/
default:
{
if(opStack.isEmpty())
{
opStack.push(val);
}else if(opStack.peek().equals(Operation.OPRATION.LEFT.getName()) || opStack.peek().equals(Operation.OPRATION.RIGHT.getName()))
{
opStack.push(val);
}else if(Operation.getInstance().getPri(exp.charAt(inx))>=Operation.getInstance().getPri(opStack.peek().charAt(0)))
{
opStack.push(val);
}else{
valStack.push(opStack.peek());
opStack.push(val);
}
}
}
}
//将运算符存到数据堆栈
while(!opStack.isEmpty())
{
valStack.push(opStack.pop());
}
String[] list=new String[valStack.size()];
valStack.toArray(list);
System.out.println(Arrays.toString(list));
String result="";
for(int len=0;len<list.length;len++)
{
result=result+list[len];
}
return result;
}
public String cal(String exp)
{
int length=exp.length();
System.out.println(" cal exp:"+exp+" length:"+length);
Stack<String> valStack =new Stack<String>();
String val=null;
Operation.OPRATION op;
for(int inx=0;inx<length;inx++)
{
val=exp.substring(inx,inx+1);
op=Operation.getInstance().getOp(exp.charAt(inx));
switch(op)
{
case OTHER:
{
valStack.push(val);
break;
}
default:{
valStack.push(String.valueOf(count(Operation.getInstance().getOp(exp.charAt(inx)),Double.valueOf(valStack.pop()),Double.valueOf(valStack.pop()))));
break;
}
}
}
System.out.println(valStack.peek());
return valStack.pop();
}
private double count(Operation.OPRATION op,double s1,double s2)
{
double result=0;
switch(op)
{
case ADD:
result=s1+s2;
break;
case MINUS:
result=s1-s2;
break;
case MUTI:
result=s1*s2;
break;
case DIVIDE:
result=s1/s2;
break;
}
return result;
}
public static void main(String[] args)
{
String exp="1*(2+3)";
exp=ReverseCal.getInstace().reverseExp(exp);
System.out.println("reverse exp:"+exp);
System.out.println(ReverseCal.getInstace().cal(exp));
}
}
