yeah568

Untitled

Sep 18th, 2014
358
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // balance_checker.cc --- Defines the BalanceChecker class that
  2. // will determine whether the stream used by given tokenizer is
  3. // balanced.
  4.  
  5. // balance_checker.cc is Copyright (C) 2014 by the University of
  6. // British Columbia, Some Rights Reserved.
  7. //
  8. // This work is licensed under the Creative Commons Attribution 4.0
  9. // International License. To view a copy of this license, visit
  10. // http://creativecommons.org/licenses/by/4.0/.
  11.  
  12.  
  13. #include "./balance_checker.h"
  14. #include <assert.h>
  15.  
  16.  
  17. namespace tokenizer {
  18. // Checks balance of opening/closing tokens. Updates stack
  19. // as going through stream
  20. //
  21. // Returns one of three types of things:
  22. //
  23. // A closing token (i.e., a token that is closing but IS NOT
  24. // opening) if a closing token did not match the preceeding opening
  25. // token.
  26. //
  27. // An opening token if the file ended without closing an opening
  28. // token.
  29. //
  30. // Or, on success, the EOF token that terminated input.
  31. Token BalanceChecker::check_balance() {
  32.   do {
  33.     // Using an apparently infinite loop that terminates under three
  34.     // conditions:
  35.     //
  36.     // (1) EOF reached and stack is empty (returns current token).
  37.     // (EOF = End of File.)
  38.     //
  39.     // (2) EOF reached and stack is non-empty (returns top of
  40.     // stack).
  41.     //
  42.     // (3) Any other unbalanced token (returns it).
  43.     //
  44.     // Why not just loop until eof is reached and then handle (1) &
  45.     // (2)? Scope.  With no assignment operator for Token, it's icky
  46.     // to get at it outside this loop's scope. :(
  47.     Token current_token = tokenizer_->next_token();
  48.     StackAction action = determine_action(token_stack_, current_token);
  49.  
  50.     switch (action) {
  51.       case kNoAction:
  52.         // Do nothing
  53.         break;
  54.       case kPopOldToken:
  55.         token_stack_.pop();
  56.         break;
  57.       case kPushNewToken:
  58.         token_stack_.push(current_token);
  59.         break;
  60.       case kReportUnbalancedToken:
  61.         // **** HANS WAS HERE!!! **** Your code looks a bit unbalanced here!
  62.         return current_token;
  63.         break;
  64.     }
  65.  
  66.     if (current_token.is_eof()) {
  67.       // Must have an empty stack; else, we'd get
  68.       // kReportUnbalancedToken at EOF.
  69.       assert(token_stack_.empty());
  70.       return current_token;
  71.     }
  72.   } while (true);  // Loop termination discussed @ start of loop.
  73. }
  74.  
  75. // Returns a stack action based on the passed stack and token.
  76. //
  77. // There are four cases to consider:
  78. //
  79. // A token that is both opening and closing (like a quotation mark
  80. // might be) acts as an opening token against an empty stack or a
  81. // stack whose top doesn't match it and gets pushed on the stack.
  82. // Against a stack whose top DOES match it, it acts as a closing token
  83. // instead and pops the token on the top of the stack.
  84. //
  85. // Otherwise, an opening token is easy: it gets pushed on the stack.
  86. //
  87. // A closing token must match the top of the stack and will then pop
  88. // it.  Otherwise, we have an unbalanced closing token.
  89. //
  90. // Finally, an EOF with something still on the stack means some
  91. // opening token was never closed. With an empty stack, it's fine!
  92. //
  93. // Note that this function is just about determining the action, NOT
  94. // doing it.  That should facilitate testing.  (No need to consider
  95. // the current state of this BalanceChecker's tokenizer or to
  96. // construct a full input stream.  Just make a stack and a token and
  97. // test what should happen with them directly.)
  98. BalanceChecker::StackAction
  99. BalanceChecker::determine_action(TokenStack const &token_stack,
  100.                                  Token const &new_token) const {
  101.   // **** HANS WAS HERE!!!! **** Case #1? We don't need no stinking Case #1.
  102.   if (tokenizer_->is_opening(new_token) && tokenizer_->is_closing(new_token)) {
  103.     if (token_stack.empty()) {
  104.       retun kPushNewToken;
  105.     } else {
  106.       Token top_of_stack = token_stack.top();
  107.       if (tokenizer_->are_matching(top_of_stack, new_token)) {
  108.         return kPopOldToken;
  109.       } else {
  110.         return kPushNewToken;
  111.       }
  112.     }
  113.   } else if (tokenizer_->is_opening(new_token)) {
  114.     // Case #2: An opener ONLY. Just push.
  115.     return kPushNewToken;
  116.   } else if (tokenizer_->is_closing(new_token)) {
  117.     // Case #3: A close ONLY. To be matching, there must be a matching
  118.     // opening token on the top of the stack (which must be non-empty).
  119.     if (token_stack.empty()) {
  120.       return kReportUnbalancedToken;
  121.     } else {
  122.       Token top_of_stack = token_stack.top();
  123.       if (tokenizer_->are_matching(top_of_stack, new_token)) {
  124.         return kPopOldToken;
  125.       } else {
  126.         return kReportUnbalancedToken;
  127.       }
  128.     }
  129.   } else if (new_token.is_eof()) {
  130.     // Case #4: Reached EOF
  131.     if (token_stack.empty()) {
  132.       return kNoAction;
  133.     } else {
  134.       return kReportUnbalancedToken;
  135.     }
  136.   } else {
  137.     // Otherwise: a "normal" token (no bracketing effect).
  138.     return BalanceChecker::kNoAction;
  139.   }
  140. }
  141. }  // namespace tokenizer
RAW Paste Data