题解 | 四则运算
四则运算
https://www.nowcoder.com/practice/9999764a61484d819056f807d2a91f1e
import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext()) {
String exp = scanner.nextLine();
//存储中缀表达式中的数字和+、-、*、/符号
Queue<String> hzExp = new ArrayBlockingQueue<>(1000);
//存储操作符的栈
Stack<Character> opStack = new Stack<>();
//用来临时存储一串数字的
StringBuilder sb = new StringBuilder();
for(int i = 0; i < exp.length(); i ++)
{
char ch = exp.charAt(i);
if(ch >= '0' &&
ch <= '9')
{
sb.append(ch);
//处理类似135这样的大于1位数的数字
//再继续看接下来的字符是否是数字
while(i + 1 < exp.length() &&
exp.charAt(i + 1) >= '0' &&
exp.charAt(i + 1) <= '9')
{
sb.append(exp.charAt(i + 1));
i ++;
}
hzExp.add(sb.toString());
sb.delete(0,sb.length());
}else if (ch == '-' )
{
//遇到的数字是负数
//3+2*{1+2*[-489/(8-6)+7]}，识别-489
if(i - 1 >= 0 &&
(exp.charAt(i - 1 ) == '(' ||
exp.charAt(i - 1) == '[' ||
exp.charAt(i - 1) == '{' ||
exp.charAt(i - 1) == '/' ) &&
i + 1 < exp.length() &&
exp.charAt(i + 1) >= '0' &&
exp.charAt(i + 1) <= '9')
{
i = i + 1;
sb.append(ch + String.valueOf(exp.charAt(i)));
//处理类似-489这样的大于1位数的负数
//再继续看接下来的字符是否是数字
while(i + 1 < exp.length() &&
exp.charAt(i + 1) >= '0' &&
exp.charAt(i + 1) <= '9')
{
sb.append(exp.charAt(i + 1));
i ++;
}
hzExp.add(sb.toString());
sb.delete(0,sb.length());
}else if(i == 0 &&
i + 1 < exp.length() &&
exp.charAt(i + 1) >= '0' &&
exp.charAt(i + 1) <= '9')
//遇到的数字是负数
//-325+2*{1+2*[4/(8-6)+7]},识别-325
{
i = i + 1;
sb.append(ch + String.valueOf(exp.charAt(i)));
//处理类似-489这样的大于1位数的负数
//再继续看接下来的字符是否是数字
while(i + 1 < exp.length() &&
exp.charAt(i + 1) >= '0' &&
exp.charAt(i + 1) <= '9')
{
sb.append(exp.charAt(i + 1));
i ++;
}
hzExp.add(sb.toString());
sb.delete(0,sb.length());
}else{
//就是1个减法操作符
//栈为空,直接入栈
if(opStack.isEmpty())
{
opStack.push(ch);
}else{
Character top = opStack.peek();
//当栈顶元素【可能的值为+，-，*，/,(】优先级大于等于-，需要弹出栈里的元素,把它们添加到hzExp队列中
while(top != null && top != '(')
{
hzExp.add(top.toString());
opStack.pop();
if(!opStack.isEmpty())
{
top = opStack.peek();
}else{
top = null;
}
}
//然后再把当前字符添加到栈中
opStack.push(ch);
}
}
}else if(ch == '+'){
//就是1个加法操作符
//栈为空,直接入栈
if(opStack.isEmpty())
{
opStack.push(ch);
}else{
Character top = opStack.peek();
//当栈顶元素【可能的值为+，-，*，/,(】优先级大于等于-，需要弹出栈里的元素,把它们添加到hzExp队列中
while(top != null && top != '(')
{
hzExp.add(top.toString());
opStack.pop();
if(!opStack.isEmpty())
{
top = opStack.peek();
}else{
top = null;
}
}
//然后再把当前字符添加到栈中
opStack.push(ch);
}
}else if(ch == '*' || ch == '/')
{
//就是1个*或者/操作符
//栈为空,直接入栈
if(opStack.isEmpty())
{
opStack.push(ch);
}else{
Character top = opStack.peek();
if(top == '*' || top == '/')
{
//栈顶元素为*或者/，其优先级和*,/相等，需要弹出它们,把它们添加到hzExp队列中
while(top != null &&
(top == '*' || top == '/'))
{
hzExp.add(top.toString());
opStack.pop();
if(!opStack.isEmpty())
{
top = opStack.peek();
}else{
top = null;
}
}
//然后再把当前字符添加到栈中
opStack.push(ch);
}else if(top == '+' || top == '-' || top == '(')
{
//栈顶元素为+或者-或(，其优先级比*,/小，不需要弹出它们,直接把ch添加到栈中
opStack.push(ch);
}
}
}else if(ch == '{' ||
ch == '[' ||
ch == '(')
{
//当ch字符为{，[,(时，直接以(形式入栈
opStack.push('(');
}else if(ch == '}' ||
ch == ']' ||
ch == ')')
{
//当ch字符为},],)时，遍历opStack，弹出元素，直到遇到(
while(!opStack.isEmpty() &&
opStack.peek() != '(')
{
Character top = opStack.pop();
hzExp.add(top.toString());
}
if(!opStack.isEmpty()){
//弹出字符(
opStack.pop();
}
}
}
//最后遍历opStack，弹出所有元素，并把元素添加到hzExp中,程序运行到这儿之后，hzExp存储的就是后缀表达式，也就是逆行波兰表达式
while(!opStack.isEmpty() )
{
Character top = opStack.pop();
hzExp.add(top.toString());
}
/* while(!hzExp.isEmpty()){
System.out.print(hzExp.poll());
//比如3+2*{1+2*[-489/(8-6)+7]}的逆波兰表达式为3212-48986-/7+*+*+
}*/
//根据逆波兰表达式借助栈计算值
Stack<Integer> digitStack = new Stack<>();
while(!hzExp.isEmpty())
{
String ele = hzExp.poll();
if(!(ele.equals("+") ||
ele.equals("-") ||
ele.equals("*") ||
ele.equals("/"))){
digitStack.push(Integer.parseInt(ele));
}else{
//弹出第1个操作数
Integer secondDig = digitStack.pop();
//弹出第2个操作数
Integer firstDig = digitStack.pop();
Integer result = null;
if(ele.equals("+"))
{
result = firstDig + secondDig;
}else if(ele.equals("-"))
{
result = firstDig - secondDig;
}else if(ele.equals("*"))
{
result = firstDig * secondDig;
}else if(ele.equals("/"))
{
result = firstDig / secondDig;
}
digitStack.push(result);
}
}
//这就是表达式的计算结果
Integer res = digitStack.pop();
System.out.println(res);
}
}
}