后续表达式 计算器
核心算法:
1.前缀表达式转后缀表达式 ->开始扫描:
2·元素为数字时,加入后缀表达式;
3·元素为运算符:
a. 若为 '(',入栈; 、
b. 若为')',则依次把栈中的的运算符加入后缀表达式中,直到出现'(',从栈中删除'(' ;
c. 若为 除括号外的其他运算符(+ - * /),当其优先级高于除'('以外的栈顶运算符时,直接入栈。否则从栈顶开始,依次弹出比当前处理的运算符优先级高和优先级相等的运算符,直到一个比它优先级低的或者遇到了一个左括号为止。
4.·当扫描的中缀表达式结束时,栈中的的所有运算符出栈;
/***
* 元素类型
* @author LENOVO
*
*/
public enum ElementsType{
NUMBER,OPERATOR
}
/**
* 封装操作元素
* @author LENOVO
*/
public class Elements {
private ElementsType elementsType;//元素类型
private Object obj;//元素值
private Integer level;//元素等级
public Elements(ElementsType elementsType, Object obj, Integer level) {
super();
this.elementsType = elementsType;
this.obj = obj;
this.level = level;
}
public Integer getLevel() {
return level;
}
public void setLevel(Integer level) {
this.level = level;
}
public ElementsType getElementsType() {
return elementsType;
}
public void setElementsType(ElementsType elementsType) {
this.elementsType = elementsType;
}
public Object getObj() {
return obj;
}
public void setObj(Object obj) {
this.obj = obj;
}
@Override
public String toString() {
return obj.toString()+" ";
}
}
import java.util.LinkedList;
/**
* 核心计算类
* @author LENOVO
*
*/
public class Count {
/**
* 分割操作符与操作数
* @param medStrObj 中序表达式
* @return
*/
public LinkedList<Elements> cutting(String medStr) {
LinkedList<Elements> medExpression=new LinkedList<Elements>();
for(int i=0;i<medStr.length();i++) {
if(i+1==medStr.length()&&(medStr.charAt(i)<='9'&&medStr.charAt(i)>='0')) {
String wait=medStr.substring(0,i+1);
medStr=medStr.substring(i,medStr.length());
Elements e=new Elements(ElementsType.NUMBER,new Double(wait),0);
medExpression.add(e);
break;
}
if((medStr.charAt(i)>='0'&&medStr.charAt(i)<='9')||medStr.charAt(i)=='.') {
continue;
}
char c=medStr.charAt(i);
if(medStr.charAt(i)=='+'||medStr.charAt(i)=='-'||medStr.charAt(i)=='*'||medStr.charAt(i)=='/'
||medStr.charAt(i)==')'||medStr.charAt(i)=='^') {
if(i!=0) {
String wait=medStr.substring(0,i);
medStr=medStr.substring(i,medStr.length());
Elements e=new Elements(ElementsType.NUMBER,new Double(wait),0);
medExpression.add(e);
}
}
String wait=medStr.substring(0,1);
medStr=medStr.substring(1,medStr.length());
i=-1;
Elements e=new Elements(ElementsType.OPERATOR,wait,c=='+'||c=='-'?1:c=='*'||c=='/'?2:c=='^'?3:4);
medExpression.add(e);
}
return medExpression;
}
/***
* 中序表达式转后续表达式
* @param medStrs 中序表达式
* @return
* @throws Exception
*/
public LinkedList<Elements> medTransSub(String medStr)throws Exception{
LinkedList<Elements> medStrObj=cutting(medStr);
LinkedList<Elements> subStrObj=new LinkedList<Elements>();
LinkedList<Elements> stack=new LinkedList<Elements>();
for(int i=0;i<medStrObj.size();i++) {
if(medStrObj.get(i).getElementsType()==ElementsType.NUMBER) {
subStrObj.addLast(medStrObj.get(i));
}else if(medStrObj.get(i).getObj().equals("(")) {
stack.addFirst(medStrObj.get(i));
}else if(medStrObj.get(i).getObj().equals(")")) {
while(true) {
Elements c=(Elements) stack.removeFirst();
if(c.getObj().equals("(")||stack.size()<=0) {
break;
}else {
subStrObj.addLast(c);
}
}
}else {
while(true) {
if((stack.size()<=0||stack.getFirst().getObj().equals("("))
||(medStrObj.get(i).getLevel()>stack.getFirst().getLevel())){
break;
}else {
Elements op=(Elements) stack.removeFirst();
subStrObj.addLast(op);
}
}
stack.addFirst(medStrObj.get(i));
}
}
while(true) {
if(stack.size()<=0) {
break;
}
subStrObj.addLast(stack.removeFirst());
}
System.out.println(subStrObj);
return subStrObj;
}
/**
* 核心计算方法
* @param medStr 中序表达式
* @return
* @throws Exception
*/
public double countCore(String medStr) throws Exception {
LinkedList<Elements> subStrObj=medTransSub(medStr);
LinkedList<Double> numberStack=new LinkedList<Double>();
for(int i=0;i<subStrObj.size();i++) {
Elements e=subStrObj.get(i);
if(e.getElementsType()==ElementsType.NUMBER) {
numberStack.addFirst((Double)e.getObj());
}else {
if(e.getObj().equals("+")) {
Double d=numberStack.removeFirst();
Double d2=numberStack.removeFirst();
numberStack.addFirst(d2+d);
}else if(e.getObj().equals("-")) {
Double d=numberStack.removeFirst();
Double d2=numberStack.removeFirst();
numberStack.addFirst(d2-d);
}else if(e.getObj().equals("*")) {
Double d=numberStack.removeFirst();
Double d2=numberStack.removeFirst();
numberStack.addFirst(d2*d);
}else if(e.getObj().equals("/")) {
Double d=numberStack.removeFirst();
Double d2=numberStack.removeFirst();
numberStack.addFirst(d2/d);
}else if(e.getObj().equals("^")){
Double d=numberStack.removeFirst();
Double d2=numberStack.removeFirst();
numberStack.addFirst(Math.pow(d2,d));
}
}
}
return numberStack.getFirst();
}
}
另附:
import java.util.Stack;
/***
* 表达式验证
* @author LENOVO
*
*/
public class Experssion {
public int experssionVaild(String medStr) {
if(!isMatch(medStr)) {
return -2;
}
if (!(medStr.charAt(0) <= '9' && medStr.charAt(0) >= '0') && medStr.charAt(0) != '(') {
return 0;
}
if (!(medStr.charAt(medStr.length() - 1) <= '9' && medStr.charAt(medStr.length() - 1) >= '0')
&& medStr.charAt(medStr.length() - 1) != ')') {
return medStr.length() - 1;
}
for (int i = 1; i < medStr.length() - 1; i++) {
char c=medStr.charAt(i);
if (!(c <= '9' && c >= '0') && c != '('
&& c != ')' && c != '+' && c != '-'
&& c != '*' && c != '/' && c != '^'&&c != '.') {
return i;
}
if ((c == '(' && (medStr.charAt(i + 1) == '+' || medStr.charAt(i + 1) == '-'
|| medStr.charAt(i + 1) == '*' || medStr.charAt(i + 1) == '/' || medStr.charAt(i + 1) == ')'))
|| (c == '(' && (medStr.charAt(i - 1) <= '9' && medStr.charAt(i - 1) >= '0'))) {
return i;
}
if ((c == ')' && (medStr.charAt(i - 1) == '+' || medStr.charAt(i - 1) == '-'
|| medStr.charAt(i - 1) == '*' || medStr.charAt(i - 1) == '/' || medStr.charAt(i - 1) == ')'))
|| (c == ')' && (medStr.charAt(i + 1) <= '9' && medStr.charAt(i + 1) >= '0'))) {
return i;
}
if (((c == '^' && !(medStr.charAt(i - 1) <= '9' && medStr.charAt(i - 1) >= '0'))
&& (c == '^' && medStr.charAt(i - 1) != ')'))
|| ((c == '^' && !(medStr.charAt(i + 1) <= '9' && medStr.charAt(i + 1) >= '0'))
&& (c == '^' && medStr.charAt(i + 1) != '('))) {
return i;
}
if (c == '.') {
if (!(medStr.charAt(i - 1) <= '9' && medStr.charAt(i - 1) >= '0')
|| !(medStr.charAt(i + 1) <= '9' && medStr.charAt(i + 1) >= '0')) {
return i;
}
} else if ((c == '+' || c == '-' || c == '*'
|| c == '/')
&& ((medStr.charAt(i + 1) == '+' || medStr.charAt(i + 1) == '-' || medStr.charAt(i + 1) == '*'
|| medStr.charAt(i + 1) == '/' || medStr.charAt(i + 1) == '^')
|| (medStr.charAt(i - 1) == '+' || medStr.charAt(i - 1) == '-'
|| medStr.charAt(i - 1) == '*' || medStr.charAt(i - 1) == '/'
|| medStr.charAt(i - 1) == '^'))) {
return i;
}
}
return -1;
}
public boolean isMatch(String s) {
Stack<Character> sc = new Stack<Character>();
char[] c = s.toCharArray();
for (int i = 0; i < c.length; i++) {
if (c[i] == '(' || c[i] == '[' || c[i] == '{') {
sc.push(c[i]);
} else if (c[i] == ')') {
if (sc.isEmpty()) {
return false;
} else {
if (sc.peek() == '(') {
sc.pop();
}
}
} else if (c[i] == ']') {
if (sc.isEmpty()) {
return false;
} else {
if (sc.peek() == '[') {
sc.pop();
}
}
} else if (c[i] == '}') {
if (sc.isEmpty()) {
return false;
} else {
if (sc.peek() == '{') {
sc.pop();
}
}
}
}
if (sc.empty()) {
return true;
} else {
return false;
}
}
}
@Test
public void testss() {
String preStr = "5*8-9/8*2+4*6";
try {
Double d=new Count().countCore(preStr);
System.out.println(d);
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
