题目在这里http://lx.lanqiao.cn/problem.page?gpid=T419
输入一个只包含加减乖除和括号的合法表达式，求表达式的值。
表达式计算虽然看起来挺简单的，但是编码起来也不是想象中的那么容易。虽说上课的时候，有讲过逆波兰表达式，但是还没动手实现过，刚好在蓝桥上看到，就动手用Java实践了一下，c++也类似。
算法主要是由两部分组成，一个是将输入的我们日常使用的中缀表达式转化为后缀的逆波兰表达式，这里可以用调度场算法实现。转换成逆波兰表达式的最主要好处是去掉了括号，同时，使得计算表达式的结果可以只遍历一次逆波兰表达式，方便计算。调度场算法类似于火车调度，从头到尾遍历表达式，出现操作数时，直接输出到结果队列，出现操作符时，弹出栈中元素直至栈顶操作符优先级大于当前操作符或者栈为空，再将当前操作符压入堆栈，当遍历完表达式时，将堆栈中的操作符依次弹出压入结果队列。如果多了括号，则出现（时，将其压入堆栈，出现）时，将堆栈中的操作符依次弹出压入结果队列，直至出现（，（不放入结果队列。具体可以 参看
https://zh.wikipedia.org/wiki/调度场算法第二部分则根据逆波兰表达式，直接计算表达式的结果。从头到尾遍历逆波兰表达式，将操作数压入堆栈，遇到操作符，则从堆栈弹出两个操作数，计算之，再把结果压入堆栈。在保证输入合法的情况下，最后结果中堆栈中只有一个元素，就是答案。具体可以参看 https://zh.wikipedia.org/wiki/逆波兰表示法
import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.Stack; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); while(cin.hasNext()){ String s = cin.nextLine(); //将中缀表达式转化为后缀表达式 Queue<Object> queue = new LinkedList<Object>(); Stack<Character> stack = new Stack<Character>(); int x = 0; boolean isInt =false; for(int i=0; i<s.length(); i++){ char ch = s.charAt(i); if(ch>='0'&&ch<='9'){ x = x*10 + ch-'0'; isInt = true; }else{ if(isInt) queue.add((Integer)x); x = 0; isInt = false; if(ch=='('){ stack.push(ch); }else if(ch==')'){ // System.out.println(stack); // System.out.println(queue); while(stack.peek()!='('){ // System.out.println(stack.peek()); queue.add(stack.pop()); } stack.pop(); }else{ while(!stack.empty() && rank(stack.peek())>=rank(ch)){ queue.add(stack.pop()); } stack.push(ch); } } } if(x!=0) queue.add(x); while(!stack.empty()) queue.add(stack.pop()); // 计算逆波兰表达式 Stack<Integer> integers = new Stack<Integer>(); for(Object object : queue){ if(object instanceof Integer){ integers.push((Integer)object); }else{ int b = integers.pop(); int a = integers.pop(); char op = (Character)object; if(op=='+') integers.push(a+b); else if(op=='-') integers.push(a-b); else if(op=='*') integers.push(a*b); else integers.push(a/b); } } System.out.println(integers.peek()); } } private static int rank(char ch){ if(ch=='+'||ch=='-'){ return 1; }else if(ch=='*' || ch=='/'){ return 2; }else{ //( ) return 0; //( ) 的优先级应该跟高，但这里为了代码的简洁，将其设为最小 } } }
