AcWing 151. Java看我
原题链接
中等
作者:
Zh1995
,
2020-08-14 16:08:05
,
所有人可见
,
阅读 548
import java.util.*;
class Main{
static LinkedList<Integer> nums=new LinkedList<>();
static LinkedList<Character> ops=new LinkedList<>();
static HashMap<Character,Integer> map=new HashMap<>();
static void cal(){
int b=nums.pollLast();
int a=nums.pollLast();
char c=ops.pollLast();
if(c=='+') nums.addLast(a+b);
if(c=='-') nums.addLast(a-b);
if(c=='*') nums.addLast(a*b);
if(c=='/') nums.addLast(a/b);
if(c=='^') nums.addLast((int)Math.pow(a,b));
}
public static void main(String args[]){
//编辑优先级,加减是1号优先级,优先级越高越优先执行
map.put('+',1); map.put('-',1); map.put('*',2); map.put('/',2); map.put('^',3);
Scanner sc=new Scanner(System.in);
String str=sc.next();
//不能有多余的右括号,因为右括号会连续弹栈两次,这样会出错。在首尾添加括号是为了保证所有的都会被计算一次
StringBuffer sb=new StringBuffer();
for(int i=0;i<str.length();i++) sb.append('(');
str=sb.toString()+str+')';
for(int i=0;i<str.length();i++){
char c=str.charAt(i);
if(c<='9' && c>='0'){
int val=0,j=i;
while(j<str.length() && str.charAt(j)<='9' && str.charAt(j)>='0')
val=val*10+(str.charAt(j++)-'0');
nums.addLast(val);
i=j-1;
}
else if(c=='(') ops.addLast(c);
else if(c==')'){
while(ops.peekLast()!='(') cal();
ops.pollLast();
}
else if(c=='-'){
//'-'可能是减号也可能是负号
//1.如果是负号的话,
//1.1负号前不能是数字,例如12-23,这里是减。并且负号前不能是右括号,例如(12)-(23),这里是减
if((i!=0 && (str.charAt(i-1)<'0' || str.charAt(i-1)>'9')) && (i!=0 && str.charAt(i-1)!=')')){
int val=0,j=i+1;
while(j<str.length() && str.charAt(j)<='9' && str.charAt(j)>='0')
val=val*10+(str.charAt(j++)-'0');
nums.addLast(-val);
i=j-1;
}
else{
while(ops.peekLast()!='(') cal();
ops.addLast(c);
}
}
else{
//计算大于等于当前优先级所有运算符('+'、'*'、'/','^')
while(!ops.isEmpty() && ops.peekLast()!='(' && map.get(ops.peekLast())>=map.get(c)) cal();
ops.addLast(c);
}
}
System.out.println(nums.pollLast());
}
}