给定一个表达式,其中运算符仅包含?+,-,*,/
(加 减 乘 整除),可能包含括号,请你求出表达式的最终值。
注意:
-
?只作为减号出现,不会作为负号出现,例如,-1+2
,(2+2)*(-(1+1)+2)
?之类表达式均不会出现。//
默认向下取整,因此Python的eval()
函数中的整除也是向下取整,在本题中不能直接使用。共一行,为给定表达式。
共一行,为表达式的结果。
表达式的长度不超过?105105。
(2+2)*(1+1)
8
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//读入输入的字符串表达式
String s = sc.next();
Map<Character,Integer> map = new HashMap<>();
map.put('+',1);
map.put('-',1);
map.put('*',2);
map.put('/',2);
Stack<Character> op = new Stack<>(); //存字符
Stack<Integer> num = new Stack<>(); //存数字
//循环遍历每一位字符
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
//数字可能存在多位
if (Character.isDigit(c)){
int x = 0; //x用来放入栈的数字 (数字不一定只有一位)
int j = i;
//要判断当前这个字符是不是数字,不能直接把c拿来判断
while (j < s.length() && Character.isDigit(s.charAt(j))){
x = x * 10 + s.charAt(j) - '0';
j++;
}
//while循环退出后的x即为要入栈的数字
num.push(x);
//此时的j指向新的一个字符(即x末尾数字的下一个),但最外层的for循环会对i自增
//只需要让i指向x的最后一位即可
i = j - 1;
} else if( c == '('){
//左括号直接入栈即可
op.push(c);
} else if( c == ')'){
//如果是右括号,因为括号的优先级最高,所以此时不需要考虑栈的优先级问题
//直接把两个括号间的内容进行计算
while (op.peek() != '('){
//这里只是对+-*/弹出,对于(并没有处理,在while外层还需要单独对while处理
eval(op,num);
}
//将左括号弹出
op.pop();
}else {
//正常字符的话: 栈顶元素的优先级 >= 当前元素的优先级,就计算
//否则就入栈
//栈内元素计算的前提是栈不能为空
//左括号以左的内容不能碰,
while (!op.empty() && op.peek() != '('
&& map.get(op.peek()) >= map.get(c)){
eval(op,num);
}
op.push(c);
}
}
//最后把字符栈里的所有元素直接计算
while (!op.empty()) eval(op,num);
System.out.println(num.peek());
}
public static void eval(Stack<Character> chars, Stack<Integer> nums){
int b = nums.pop();
int a = nums.pop();
char c = chars.pop();
if (c == '+'){
nums.push(a + b);
} else if (c == '-'){
nums.push(a - b);
}else if (c == '*'){
nums.push(a * b);
}else{
nums.push(a / b);
}
}
}