|
|
package Stack;
|
|
|
|
|
|
import java.util.ArrayList;
|
|
|
import java.util.List;
|
|
|
import java.util.Stack;
|
|
|
|
|
|
|
|
|
public class Calculation{
|
|
|
//将中缀表达式转为List
|
|
|
public static List<String> InfixtoList(String s){
|
|
|
List<String> l=new ArrayList<String>();
|
|
|
int i=0;//用于遍历中缀表达式字符串
|
|
|
String splicing;//对多位数的拼接
|
|
|
char c;//遍历每一个字符，就被列入c
|
|
|
do {//如果c是非数字，就加入到l中
|
|
|
if((c=s.charAt(i))<48||(c=s.charAt(i))>57) {
|
|
|
l.add(""+c);
|
|
|
i++;
|
|
|
}else {//如果是一个数还需要考虑多位数的问题
|
|
|
splicing="";//先见str置成""
|
|
|
while(i<s.length() && (c=s.charAt(i))>=48 && (c=s.charAt(i))<=57) {
|
|
|
splicing+=c;
|
|
|
i++;
|
|
|
}
|
|
|
l.add(splicing);
|
|
|
}
|
|
|
|
|
|
}while(i<s.length());
|
|
|
return l;
|
|
|
}
|
|
|
//将得到List转为后缀表达式
|
|
|
public static List<String> ListtoSuffix(List<String> l){
|
|
|
Stack<String> s1=new Stack<String> ();
|
|
|
List<String> s2=new ArrayList<String> ();
|
|
|
//遍历l
|
|
|
for(String item: l) {
|
|
|
//如果是一个数则加入到s2
|
|
|
if(item.matches("\\d+"))
|
|
|
{
|
|
|
s2.add(item);
|
|
|
}else if(item.equals("(")){
|
|
|
s1.push(item);
|
|
|
}else if(item.equals(")")){
|
|
|
while(!s1.peek().equals("(")) {//查看s1中的元素是否等于(
|
|
|
s2.add(s1.pop());
|
|
|
}
|
|
|
s1.pop();//将(弹出，消除(
|
|
|
|
|
|
}else {
|
|
|
//当item的优先级小于等于栈顶的优先级将s1栈顶运算符弹出压入到s2中，再次与s1中的栈顶运算符比较
|
|
|
while(s1.size()!=0 && Operation.getValue(s1.peek())>=Operation.getValue(item)) {
|
|
|
s2.add(s1.pop());
|
|
|
}
|
|
|
//还需要将item压入栈中
|
|
|
s1.push(item);
|
|
|
}
|
|
|
}
|
|
|
while(s1.size()!=0) {
|
|
|
s2.add(s1.pop());
|
|
|
}
|
|
|
return s2;
|
|
|
|
|
|
}
|
|
|
//计算
|
|
|
public static int calculate(List<String> l) {
|
|
|
//创建一个栈
|
|
|
Stack<String> stack=new Stack<String>();
|
|
|
for(String item: l) {
|
|
|
if(item.matches("\\d+")) {//匹配的是多位数
|
|
|
stack.push(item);
|
|
|
}
|
|
|
else {
|
|
|
int num2=Integer.parseInt(stack.pop());
|
|
|
int num1=Integer.parseInt(stack.pop());
|
|
|
int res=0;
|
|
|
if(item.equals("+")) {
|
|
|
res=num1+num2;
|
|
|
}else if(item.equals("-")) {
|
|
|
res=num1-num2;
|
|
|
}else if(item.equals("*")) {
|
|
|
res=num1*num2;
|
|
|
}else if(item.equals("/")) {
|
|
|
res=num1/num2;
|
|
|
}else {
|
|
|
throw new RuntimeException("运算符有误");
|
|
|
}
|
|
|
|
|
|
//把res入栈
|
|
|
stack.push(res+"");//把整数转为字符串
|
|
|
|
|
|
}
|
|
|
}
|
|
|
//最后留在stack中的数据就是运算结果
|
|
|
return Integer.parseInt(stack.pop());
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
//编写一个类Operation可以返回一个运算符对应的优先级
|
|
|
class Operation{
|
|
|
private static int ADD=1;
|
|
|
private static int SUB=1;
|
|
|
private static int MUL=2;
|
|
|
private static int DIV=2;
|
|
|
//写一个方法返回对应的优先级
|
|
|
public static int getValue(String operation) {
|
|
|
int result=0;
|
|
|
switch (operation) {
|
|
|
case "+":
|
|
|
result=ADD;
|
|
|
break;
|
|
|
case "-":
|
|
|
result=SUB;
|
|
|
break;
|
|
|
case "*":
|
|
|
result=MUL;
|
|
|
break;
|
|
|
case "/":
|
|
|
result=DIV;
|
|
|
break;
|
|
|
default:
|
|
|
//System.out.println("不存在该运算符");
|
|
|
break;
|
|
|
}
|
|
|
return result;
|
|
|
}
|
|
|
}
|
