使用辅助栈解题
表达式求值
http://www.nowcoder.com/questionTerminal/e06d50b938d24a2b8a2c14edebee5478
我们要做的就是利用单调栈让栈里至只剩下true,and,or三种字符串,接下来就好比较了。
package bishi; import java.util.Scanner; import java.util.Stack; public class Solution { public static void main(String[] args) { //将输入的字符串分割成一个字符串数组 Scanner sc = new Scanner(System.in); String[] words = sc.nextLine().split(" "); Stack<String> stack = new Stack<>(); //对数组中的字符串进行遍历 for(int i = 0; i < words.length; i++){ String cur = words[i]; //如果字符串为true或者false if(cur.equals("true") || cur.equals("false")){ //栈为空就直接入栈 if(stack.isEmpty()){ stack.push(cur); }else{ //不为空就检查栈顶元素,如果也为true或者false,就输出error String top = stack.peek(); if(top.equals("true") || top.equals("false")){ System.out.println("error"); return; }else{ //如果栈顶元素为or,直接入栈 if(top.equals("or")){ stack.push(cur); }else{ //如果栈顶元素为and,先弹出and,再弹出and下面的元素进行比较 stack.pop(); String tmp = stack.pop(); //如果都为false,就压入false,如果有一个不为false,肯定就是压入true了。 if(cur.equals("false") || tmp.equals("false")){ stack.push("false"); }else{ stack.push("true"); } } } } }else{ //如果元素是and或者or的话,栈为空,肯定不合法,输出error。 if(stack.isEmpty()){ System.out.println("error"); return; }else{ //不为空,就与栈顶元素比较,如果为and或者or,也不合法,如果是true或者false,就正常压栈。 String top = stack.peek(); if(top.equals("and") || top.equals("or")){ System.out.println("error"); return; }else{ stack.push(cur); } } } } //遍历完之后先检查栈顶元素是否合法 if(!stack.isEmpty() && (stack.peek().equals("and") || stack.peek().equals("or"))){ System.out.println("error"); return; } //如果合法,循环弹出元素,只要碰到有一个为true,就直接输出true,因为栈里只有or了。 while(!stack.isEmpty()){ String cur = stack.pop(); if(cur.equals("true")){ System.out.println("true"); return; } } //循环结束,栈空了都没有true,那就只能输出false了 System.out.println("false"); } }