Evaluating Parenthesized Boolean Expressions (Using Stacks)


/ Published in: Java
Save to your folder(s)

An [example][id]. Then, **anywhere**
else in the doc, define the link:

[id]: http://example.com/ "Title"


Copy this code and paste it in your HTML
  1. // This program reads a reads and evaluates fully parenthesized Boolean
  2. // expressions. The purpose is to illustrate a fundamental use of stacks.
  3.  
  4.  
  5. import java.util.Stack;
  6. import java.util.Scanner;
  7. import java.util.regex.Pattern;
  8.  
  9. public class KauffmanW7_LargeProgram05_EvalBoolean
  10. {
  11.  
  12. public static void main(String[ ] args)
  13. {
  14. Scanner stdin = new Scanner(System.in);
  15. String expression;
  16. boolean answer;
  17.  
  18. // Testing Expressions.
  19. expression = "(5>1)";
  20. answer = evaluate(expression);
  21. System.out.print("Test01: " + expression + " evaluated as ");
  22. if (answer == true) {
  23. System.out.println("true, which is correct.");
  24. }
  25. else {
  26. System.out.println("false, which is WRONG.");
  27. }
  28.  
  29. expression = "(5>=1)";
  30. answer = evaluate(expression);
  31. System.out.print("Test02: " + expression + " evaluated as ");
  32. if (answer == true) {
  33. System.out.println("true, which is correct.");
  34. }
  35. else {
  36. System.out.println("false, which is WRONG.");
  37. }
  38.  
  39. expression = "(5<1)";
  40. answer = evaluate(expression);
  41. System.out.print("Test03: " + expression + " evaluated as ");
  42. if (answer == true) {
  43. System.out.println("true, which is WRONG.");
  44. }
  45. else {
  46. System.out.println("false, which is correct.");
  47. }
  48.  
  49. expression = "(5<=1)";
  50. answer = evaluate(expression);
  51. System.out.print("Test04: " + expression + " evaluated as ");
  52. if (answer == true) {
  53. System.out.println("true, which is WRONG.");
  54. }
  55. else {
  56. System.out.println("false, which is correct.");
  57. }
  58.  
  59. expression = "(5==1)";
  60. answer = evaluate(expression);
  61. System.out.print("Test05: " + expression + " evaluated as ");
  62. if (answer == true) {
  63. System.out.println("true, which is WRONG.");
  64. }
  65. else {
  66. System.out.println("false, which is correct.");
  67. }
  68.  
  69. expression = "(5!=1)";
  70. answer = evaluate(expression);
  71. System.out.print("Test06: " + expression + " evaluated as ");
  72. if (answer == true) {
  73. System.out.println("true, which is correct.");
  74. }
  75. else {
  76. System.out.println("false, which is WRONG.");
  77. }
  78.  
  79. expression = "(10 > 5)";
  80. answer = evaluate(expression);
  81. System.out.print("Test07: " + expression + " evaluated as ");
  82. if (answer == true) {
  83. System.out.println("true, which is correct.");
  84. }
  85. else {
  86. System.out.println("false, which is WRONG.");
  87. }
  88.  
  89. expression = "(10 >= 5)";
  90. answer = evaluate(expression);
  91. System.out.print("Test08: " + expression + " evaluated as ");
  92. if (answer == true) {
  93. System.out.println("true, which is correct.");
  94. }
  95. else {
  96. System.out.println("false, which is WRONG.");
  97. }
  98.  
  99. expression = "(10 < 5)";
  100. answer = evaluate(expression);
  101. System.out.print("Test09: " + expression + " evaluated as ");
  102. if (answer == true) {
  103. System.out.println("true, which is WRONG.");
  104. }
  105. else {
  106. System.out.println("false, which is correct.");
  107. }
  108.  
  109. expression = "(10 <= 5)";
  110. answer = evaluate(expression);
  111. System.out.print("Test10: " + expression + " evaluated as ");
  112. if (answer == true) {
  113. System.out.println("true, which is WRONG.");
  114. }
  115. else {
  116. System.out.println("false, which is correct.");
  117. }
  118.  
  119. expression = "(10 == 5)";
  120. answer = evaluate(expression);
  121. System.out.print("Test11: " + expression + " evaluated as ");
  122. if (answer == true) {
  123. System.out.println("true, which is WRONG.");
  124. }
  125. else {
  126. System.out.println("false, which is correct.");
  127. }
  128.  
  129. expression = "(10 != 5)";
  130. answer = evaluate(expression);
  131. System.out.print("Test12: " + expression + " evaluated as ");
  132. if (answer == true) {
  133. System.out.println("true, which is correct.");
  134. }
  135. else {
  136. System.out.println("false, which is WRONG.");
  137. }
  138.  
  139. expression = "((10 > 5) && (10 > 15))";
  140. answer = evaluate(expression);
  141. System.out.print("Test13: " + expression + " evaluated as ");
  142. if (answer == true) {
  143. System.out.println("true, which is WRONG.");
  144. }
  145. else {
  146. System.out.println("false, which is correct.");
  147. }
  148.  
  149. expression = "((10 > 5) || (10 > 15))";
  150. answer = evaluate(expression);
  151. System.out.print("Test14: " + expression + " evaluated as ");
  152. if (answer == true) {
  153. System.out.println("true, which is correct.");
  154. }
  155. else {
  156. System.out.println("false, which is WRONG.");
  157. }
  158.  
  159. expression = "(((10 > 5) && (10 > 15)) || (20 > 15))";
  160. answer = evaluate(expression);
  161. System.out.print("Test15: " + expression + " evaluated as ");
  162. if (answer == true) {
  163. System.out.println("true, which is correct.");
  164. }
  165. else {
  166. System.out.println("false, which is WRONG.");
  167. }
  168.  
  169. expression = "(((10 > 5) || (10 > 15)) && (15 >= 20))";
  170. answer = evaluate(expression);
  171. System.out.print("Test16: " + expression + " evaluated as ");
  172. if (answer == true) {
  173. System.out.println("true, which is WRONG.");
  174. }
  175. else {
  176. System.out.println("false, which is correct.");
  177. }
  178.  
  179. expression = "(!(5<1))";
  180. answer = evaluate(expression);
  181. System.out.print("Test17: " + expression + " evaluated as ");
  182. if (answer == true) {
  183. System.out.println("true, which is correct.");
  184. }
  185. else {
  186. System.out.println("false, which is WRONG.");
  187. }
  188.  
  189. expression = "(!(5>1))";
  190. answer = evaluate(expression);
  191. System.out.print("Test18: " + expression + " evaluated as ");
  192. if (answer == true) {
  193. System.out.println("true, which is WRONG.");
  194. }
  195. else {
  196. System.out.println("false, which is correct.");
  197. }
  198.  
  199.  
  200.  
  201. answer = query(stdin, "\nWould you like to try some expressions of your own?");
  202. if (!answer) System.exit(0);
  203.  
  204.  
  205.  
  206. System.out.println("\nPlease type a Boolean expression made from");
  207. System.out.println("comparison between unsigned numbers, and the");
  208. System.out.println("operations && (AND) and || (OR). The ");
  209. System.out.println("expression must be fully parenthesized.");
  210.  
  211. do
  212. {
  213. System.out.print("Your expression: ");
  214. expression = stdin.nextLine( );
  215. try
  216. {
  217. answer = evaluate(expression);
  218. System.out.println("The value is " + answer);
  219. }
  220. catch (Exception e)
  221. {
  222. System.out.println("Error." + e.toString( ));
  223. }
  224. }
  225. while (query(stdin, "Another string?"));
  226.  
  227. System.out.println("All numbers are interesting.");
  228. }
  229.  
  230.  
  231. public static boolean query(Scanner input, String prompt) {
  232. String answer;
  233.  
  234. System.out.print(prompt + " [Y or N]: ");
  235. answer = input.nextLine( ).toUpperCase( );
  236. while (!answer.startsWith("Y") && !answer.startsWith("N"))
  237. {
  238. System.out.print("Invalid response. Please type Y or N: ");
  239. answer = input.nextLine( ).toUpperCase( );
  240. }
  241.  
  242. return answer.startsWith("Y");
  243. }
  244.  
  245.  
  246. public static boolean evaluate(String s) {
  247. // Precondition: The string is a fully parenthesized Boolean expression
  248. // formed from non-negative numbers, parentheses, comparisons, and the three
  249. // logical operations: !(NOT, unary), && (AND, binary), and || (OR, binary).
  250. // Postcondition: The string has been evaluated and the value returned.
  251. // Exceptions: Can throw an NumberFormatException if the expression contains
  252. // characters other than digits, operations, parentheses and whitespace.
  253. // Can throw IllegalArgumentException if the input line is an
  254. // illegal expression, such as unbalanced parentheses or an unknown symbol.
  255.  
  256. // KEY
  257. //****************
  258. // >= G *
  259. // <= L *
  260. // != N *
  261. // || O *
  262. // && A *
  263. // == E *
  264. //****************
  265.  
  266. s = s.replace(">=","G");
  267. s = s.replace("<=","L");
  268. s = s.replace("!=","N");
  269. s = s.replace("||","O");
  270. s = s.replace("&&","A");
  271. s = s.replace("==","E");
  272. // System.out.println(s);
  273. Scanner input = new Scanner(s);
  274. Stack<Integer> numbers = new Stack<Integer>( );
  275. Stack<Character> operations = new Stack<Character>( );
  276. Stack<Boolean> booleans = new Stack<Boolean>( );
  277. String next;
  278. char first;
  279.  
  280. while (input.hasNext( )) {
  281. if (input.hasNext(UNSIGNED_INT)) {
  282. next = input.findInLine(UNSIGNED_INT);
  283. numbers.push(new Integer(next));
  284. }
  285. else {
  286. next = input.findInLine(CHARACTER);
  287. first = next.charAt(0);
  288.  
  289. switch (first) {
  290. case '>': // Greater Than
  291. case 'G': // >= Greater Than or Equal to.
  292. case '<': // Less Than
  293. case 'L': // Less Than or Equal to.
  294. case 'E': // == Equal
  295. case 'N': // != Not Equal
  296. case '!': // Not
  297. case 'A': // && And
  298. case 'O': // || Or
  299. operations.push(first);
  300. break;
  301. case ')': // Right parenthesis
  302. evaluateStackTops(numbers, operations,booleans);
  303. break;
  304. case '(': // Left parenthesis
  305. break;
  306. default : // Illegal character
  307. throw new IllegalArgumentException("Illegal character");
  308. }
  309. }
  310. }
  311. if (booleans.size( ) != 1)
  312. throw new IllegalArgumentException("Illegal input expression" );
  313.  
  314. return booleans.pop( );
  315. }
  316.  
  317.  
  318. public static boolean evalBoolean(int oper1, int oper2, char bool) {
  319. switch (bool) {
  320. case '>': // Greater Than
  321. return (oper1 > oper2);
  322. case 'G': // >= Greater Than or Equal to.
  323. return (oper1 >= oper2);
  324. case '<': // Less Than
  325. return (oper1 < oper2);
  326. case 'L': // Less Than or Equal to.
  327. return (oper1 <= oper2);
  328. case 'E': // == Equal
  329. return (oper1 == oper2);
  330. case 'N': // != Not Equal
  331. return (oper1 != oper2);
  332. default : // This statement should be unreachable since only the aforementioned values get sent to the method...
  333. throw new IllegalArgumentException("Illegal operation");
  334. }
  335. }
  336.  
  337. public static void evaluateStackTops(Stack<Integer> numbers, Stack<Character> operations,Stack<Boolean> booleans) {
  338. int operand1, operand2;
  339. boolean bool1,bool2;
  340. if (operations.size( ) < 1)
  341. throw new IllegalArgumentException("Illegal expression (Operations Stack Underflow)");
  342. char oper = operations.pop();
  343.  
  344. switch (oper) {
  345. case '>': // Greater Than
  346. case 'G': // >= Greater Than or Equal to.
  347. case '<': // Less Than
  348. case 'L': // Less Than or Equal to.
  349. case 'E': // == Equal
  350. case 'N': // != Not Equal
  351. if (numbers.size( ) < 2)
  352. throw new IllegalArgumentException("Illegal expression (Numbers Stack Underflow)");
  353. operand2 = numbers.pop( );
  354. operand1 = numbers.pop( );
  355. booleans.push(evalBoolean(operand1,operand2,oper));
  356. break;
  357.  
  358. case '!':
  359. if (booleans.size( ) < 1)
  360. throw new IllegalArgumentException("Illegal expression (Booleans Stack Underflow)");
  361. booleans.push (!(booleans.pop( )));
  362. break;
  363.  
  364. case 'A':
  365. case 'O':
  366. if (booleans.size( ) < 2)
  367. throw new IllegalArgumentException("Illegal expression (Booleans Stack Underflow)");
  368. bool2 = booleans.pop( );
  369. bool1 = booleans.pop( );
  370. if (oper == 'A')
  371. booleans.push ( (bool1 && bool2));
  372. else
  373. booleans.push ( (bool1 || bool2));
  374. break;
  375. default :
  376. throw new IllegalArgumentException("Illegal operation (Unknown Character)");
  377. }
  378. }
  379.  
  380. // These patterns are from Appendix B of Data Structures and Other Objects.
  381. // They may be used in hasNext and findInLine to read certain patterns
  382. // from a Scanner.
  383. public static final Pattern CHARACTER = Pattern.compile("\\S.*?");
  384. public static final Pattern UNSIGNED_INT = Pattern.compile("\\d+.*?");
  385. }

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.