AcWing 151. 表达式计算4-Java
原题链接
中等
作者:
xdk
,
2021-03-11 17:51:54
,
所有人可见
,
阅读 408
import java.io.*;
import java.util.*;
public class Main {
static Stack<Integer> nums = new Stack<>();
static Stack<Character> ops = new Stack<>();
static void eval() {
int b = nums.pop(), a = nums.pop();
char c = ops.pop();
int r = 0;
if (c == '+') r = a + b;
else if (c == '-') r = a - b;
else if (c == '*') r = a * b;
else if (c == '/') r = a / b;
else r = (int) Math.pow(a, b);
nums.push(r);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
if (str.charAt(0) == '-' || str.charAt(0) == '+') str = "0" + str;
StringBuilder left = new StringBuilder();
for (int i = 0; i < str.length(); i++) left.append('('); //先加左括号,变成合法前缀
str = left.append(str).append(')').toString(); //加')',可以计算最后一步结果
char[] ch = str.toCharArray();
int n = ch.length;
for (int i = 0; i < n; i++) {
char c = ch[i];
if (Character.isDigit(c)) {
int j = i, t = 0;
while (Character.isDigit(ch[j])) t = t * 10 + (ch[j++] - '0');
nums.push(t);
i = j - 1;
} else {
if (c == ' ') continue;
if (c == '(') ops.push(c);
else if (c == ')') {
while (ops.peek() != '(') eval();
ops.pop();
}
else if (c == '+' || c == '-') {
if (c == '-' && i != 0 && !Character.isDigit(ch[i - 1]) && ch[i - 1] != ')') {
if (ch[i + 1] == '(') {
nums.push(-1);
ops.push('*');
} else {
int j = i + 1, t = 0;
while (Character.isDigit(ch[j])) t = t * 10 + (ch[j++] - '0');
nums.push(-t);
i = j - 1;
}
} else { //由于+ -优先级最低,如果栈里有其他运算符,直接计算
while (ops.peek() != '(') eval();
ops.push(c);
}
} else if (c == '*' || c == '/') {
while (ops.peek() == '*' || ops.peek() == '/' || ops.peek() == '^') eval();
ops.push(c);
} else if (c == '^') {
while (ops.peek() == '^') eval();
ops.push(c);
} else System.out.println("invalid operator!");
}
}
System.out.println(nums.pop());
}
}