AcWing 3302. 表达式求值(java)
原题链接
简单
作者:
小黎Wing
,
2021-03-20 08:51:36
,
所有人可见
,
阅读 535
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
// 2+4*5-(3+4)*5-2*8
public class Main {
static Map<String, Integer> m = new HashMap<>();
public static void main(String[] args) {
m.put("*",2);
m.put("/",2);
m.put("+",1);
m.put("-",1);
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
String s = sc.next();
Tree t = new Tree(s, m);
System.out.println(t.compute(t.root));
}
}
}
class Tree{
Node root;
Map<String, Integer> m;//优先级
public Tree(String s,Map m) {
this.m = m;
this.root = create(s);
}
public Node create(String s){ //创建表达式二叉树
StringTokenizer stz = new StringTokenizer(s,"+-*/()",true);
Stack<String> s1 = new Stack<>();//运算符栈
Stack<Node> s2 = new Stack<>();//数字栈
while(stz.hasMoreTokens()){
String t = stz.nextToken();
if("+-*/()".contains(t)){
while(true){
if(s1.isEmpty()||t.equals("(")){
s1.push(t);
break;
}else if(t.equals(")")){
String p = s1.pop();
if(p.equals("(")) {//碰到左括号,弹出
break;
}else {//弹出建立树(运算)
Node right = s2.pop();
Node left = s2.pop();
Node r = new Node(p,left,right);//弹出,建立根节点
s2.push(r);//再压回栈中
}
}else if(s1.peek().equals("(")||m.get(t)>m.get(s1.peek())){
s1.push(t);
break;
}else{
Node right = s2.pop();
Node left = s2.pop();
Node r = new Node(s1.pop(),left,right);//弹出,建立根节点
s2.push(r);//再压回栈中
}
}
}else{//数字
s2.push(new Node(t));
}
}
//处理剩下的运算符
while(!s1.isEmpty()) {
Node right = s2.pop();
Node left = s2.pop();
Node r = new Node(s1.pop(),left,right);//弹出,建立根节点
s2.push(r);//再压回栈中
}
return s2.pop();
}
public int compute(Node p) {
if(p!=null) {
if("+-*/".contains(p.d)) {
int l = compute(p.left);
int r = compute(p.right);
if(p.d.equals("+")) {
return l+r;
}else if(p.d.equals("-")) {
return l-r;
}else if(p.d.equals("*")) {
return l*r;
}else if(p.d.equals("/")) {
return l/r;
}
}
return Integer.parseInt(p.d);
}
return -9999999;
}
}
class Node{
String d;
Node left,right;
public Node(String d) {
super();
this.d = d;
}
public Node(String d, Node left, Node right) {
super();
this.d = d;
this.left = left;
this.right = right;
}
public String toString() {
return this.d.toString();
}
}