From 126b168ea2a9b63793b827cb5d6c128c781b17c9 Mon Sep 17 00:00:00 2001 From: NilsForssen Date: Mon, 9 Oct 2023 11:29:52 +0200 Subject: [PATCH] Restructuring --- src/postfix.cc | 129 ++++++++++++++++++++++++++++++++++++ src/postfix.h | 48 ++++++++++++++ src/token.cc | 163 ++++++++++++++++++++++++++++++++++++++++++++++ src/token.h | 78 ++++++++++++++++++++++ src/token_test.cc | 146 +++++++++++++++++++++++++++++++++++++++++ src/uppgift13.cc | 15 +++++ 6 files changed, 579 insertions(+) create mode 100644 src/postfix.cc create mode 100644 src/postfix.h create mode 100644 src/token.cc create mode 100644 src/token.h create mode 100644 src/token_test.cc create mode 100644 src/uppgift13.cc diff --git a/src/postfix.cc b/src/postfix.cc new file mode 100644 index 0000000..a51f184 --- /dev/null +++ b/src/postfix.cc @@ -0,0 +1,129 @@ +#include "postfix.h" +#include "token.h" + +#include +#include +#include +#include +#include + +#include +#include +#include + +// PUBLIC + +Postfix::Postfix(std::string const& infix_string) : expr{} +{ + std::istringstream is{infix_string}; + expr = make_postfix(is); +} + +std::string Postfix::to_string() const +{ + std::ostringstream os; + std::copy( std::begin(expr), std::end(expr), + std::ostream_iterator{os, " "}); + return os.str(); +} + +Postfix::operator std::string() const +{ + return to_string(); +} + +bool Postfix::operator==(std::string const& rhs) const +{ + return to_string() == rhs; +} + + +// PRIVATE + +// right associative operators have input priority > stack priority +// left associative operators have input priority < stack priority +const Postfix::priority_table Postfix::operator_table { + // {symbol, input prio, stack prio} + {"^", {8, 7}}, + {"*", {5, 6}}, + {"/", {5, 6}}, + {"%", {5, 6}}, + {"+", {3, 4}}, + {"-", {3, 4}}, + {"=", {2, 1}} +}; + +bool Postfix::is_operator(const std::string& token) +{ + // C++20: return operator_table.contains( token ); + return ( operator_table.count( token ) > 0 ); +} + +Postfix::expression Postfix::make_postfix(std::istream& is, bool match_parenthesis) const +{ + using namespace std::literals; // for string literals ""s + + op_stack operator_stack; + expression postfix; + Token token; + int unused_operands{0}; + + while (is >> token && token != ")"s ) + { + if ( is_operator(token) ) + { + while ( ! operator_stack.empty() && + operator_table.at(token).input <= + operator_table.at(operator_stack.top()).stack ) + { + postfix.push_back( operator_stack.top() ); + unused_operands -= 1; // uses 2 but creates 1 + operator_stack.pop(); + } + operator_stack.push(token); + } + else if (token == "("s) + { + expression parentesis{ make_postfix(is, true) }; + std::copy( std::begin(parentesis), std::end(parentesis), std::back_inserter(postfix) ); + unused_operands += 1; // entire postix is 1 operand + } + else + { + postfix.push_back( token ); + unused_operands += 1; + } + } + + if ( postfix.empty() && match_parenthesis && token == ")"s ) + { + throw Infix_Error{"Empty parenthesis"}; + } + + if ( match_parenthesis && token != ")"s ) + { + throw Infix_Error{"Missing ending parenthesis"}; + } + + if ( ! match_parenthesis && token == ")"s ) + { + throw Infix_Error{"Missing starting parenthesis"}; + } + + while ( ! operator_stack.empty() ) + { + postfix.push_back( operator_stack.top() ); + unused_operands -= 1; // uses 2 but creates 1 + operator_stack.pop(); + } + + if ( unused_operands != 1 ) // the last one is the answer + { + if ( unused_operands > 1 ) + throw Infix_Error{"Missing operator"}; + else + throw Infix_Error{"Missing operand"}; + } + + return postfix; +} diff --git a/src/postfix.h b/src/postfix.h new file mode 100644 index 0000000..3d3a69c --- /dev/null +++ b/src/postfix.h @@ -0,0 +1,48 @@ +#ifndef POSTFIX_H +#define POSTFIX_H + +#include +#include +#include +#include +#include +#include + +class Infix_Error : public std::logic_error +{ + using std::logic_error::logic_error; +}; + +// Creates a Postfix from a given infix string. All operands and +// operators are required to be separated by at least one space. +class Postfix +{ +public: + Postfix(std::string const& infix_string); + + std::string to_string() const; + operator std::string() const; + bool operator==(std::string const& rhs) const; + +private: + using op_stack = std::stack; + using expression = std::vector; + + expression expr; + + struct priority + { + int input; + int stack; + }; + + using priority_table = std::map; + + static const priority_table operator_table; + + static bool is_operator(const std::string& token); + + expression make_postfix(std::istream& is, bool match_parenthesis = false) const; +}; + +#endif diff --git a/src/token.cc b/src/token.cc new file mode 100644 index 0000000..65db2cd --- /dev/null +++ b/src/token.cc @@ -0,0 +1,163 @@ +#include +#include +#include +#include +#include +#include + +#include "token.h" + +using namespace std; + +// Public + +set const Token::default_operators{ + "+", "-", "*", "/", "%", "^", "=", "(", ")", "?", "£", "$" + }; + +string const Token::default_separators{" \t\n\r"}; + +Token::Token(set const& ops, string const& sep) + : operators{ops}, separators{sep}, token{} +{ +} + +istream& operator>>(istream& iss, Token& t) +{ + return t.next(iss); +} + +ostream& operator<<(ostream& oss, Token const& t) +{ + return oss << t.token; +} + +bool Token::is_operator() const +{ + return operators.count( token ) == 1; +} + +bool Token::is_integer() const +{ + return all_of(token.begin(), token.end(), ::isdigit); +} + +bool Token::is_decimal() const +{ + bool valid_chars = all_of(token.begin(), token.end(), [](char c)->bool + { + return c == '.' || isdigit(c); + }); + bool one_dot = count(token.begin(), token.end(), '.') == 1; + return valid_chars && one_dot; +} + +bool Token::is_identifier() const +{ + return all_of(token.begin(), token.end(), [](char c)->bool + { + return c == '_' || isalnum(c); + }); +} + +// Private + +bool Token::is_separator(int c) const +{ + return ( separators.find(c) != string::npos ); +} + +bool Token::is_delimeter(int c) const +{ + if ( c == -1 ) // Traits::eof() + return true; + + if ( is_separator( c ) ) + return true; + + auto b{ operators.begin() }; + auto e{ operators.end() }; + + for ( ; b != e; ++b ) + { + if ( b->at(0) == c ) + return true; + } + return false; +} + +bool Token::is_candidate() const +{ + auto b{ operators.begin() }; + auto e{ operators.end() }; + + for ( ; b != e; ++b ) + { + if ( b->find( token ) == 0 && *b != token ) + return true; + } + return false; +} + +void Token::append(int c) +{ + token.push_back( static_cast(c) ); +} + +void Token::ignore_separators(istream& iss) +{ + auto c{ iss.peek() }; + + while ( c != -1 ) // Traits::eof() + { + if ( ! is_separator( c ) ) + return; + + iss.get(); + c = iss.peek(); + } +} + +istream& Token::next(istream& iss) +{ + token.clear(); + + ignore_separators( iss ); + + auto c{ iss.peek() }; + + bool prev_is_op{false}; + + while ( c != -1 ) // Traits::eof() + { + append( c ); + + bool is_op{ is_operator() }; + bool is_can{ is_candidate() }; + bool is_del{ is_delimeter(c) }; + + if ( is_op && ! is_can ) + { + iss.get(); + return iss; + } + + if ( prev_is_op && ! is_op && ! is_can ) + { + token.pop_back(); + return iss; + } + + if ( is_del && ! is_can ) + { + token.pop_back(); + return iss; + } + + prev_is_op = is_op; + iss.get(); + c = iss.peek(); + } + + return iss; +} diff --git a/src/token.h b/src/token.h new file mode 100644 index 0000000..35bfd0e --- /dev/null +++ b/src/token.h @@ -0,0 +1,78 @@ +#ifndef TOKEN_H +#define TOKEN_H + +#include +#include +#include + +// A class to read strings from an istream just like std::string, +// but tokens are separated not only by space, but also by operators. +// +// You should be able to just change from "std::string" to "Token" in +// your program unless you do something special with your strings. +// +// Tokens can be classified as integers, deciamls, identifiers or operators. +// +class Token +{ +public: + + // interoperability with standard library (STL) + using token_t = std::string; + + using value_type = token_t::value_type; + using size_type = token_t::size_type; + using pointer = token_t::pointer; + using reference = token_t::reference; + using iterator = token_t::const_iterator; + + iterator begin() const { return token.begin(); } + iterator end() const { return token.end(); } + size_type size() const { return token.size(); } + size_type length() const { return token.length(); } + value_type at(int i) const { return token.at(i); } + + // static constants for default values + static std::set const default_operators; + static std::string const default_separators; + + // public members + Token(std::set const& operators = default_operators, + std::string const& separators = default_separators); + + friend std::istream& operator>>(std::istream& iss, Token& t); + + friend std::ostream& operator<<(std::ostream& oss, Token const& t); + + operator std::string() const { return token; } + + bool operator==(std::string const& rhs) { return token == rhs; } + bool operator!=(std::string const& rhs) { return token != rhs; } + + bool is_operator() const; + bool is_integer() const; + bool is_decimal() const; + bool is_identifier() const; + +private: + + // help functions + bool is_delimeter(int c) const; + bool is_separator(int c) const; + + bool is_candidate() const; + + void append(int c); + void ignore_separators(std::istream& iss); + + std::istream& next(std::istream& iss); + + // data members + std::set const& operators; + std::string const& separators; + std::string token; + + friend class Token_Private_Tester; +}; + +#endif diff --git a/src/token_test.cc b/src/token_test.cc new file mode 100644 index 0000000..39cc98e --- /dev/null +++ b/src/token_test.cc @@ -0,0 +1,146 @@ +#define CATCH_CONFIG_RUNNER +#include "catch.hpp" + +#include +#include + +#include "token.h" + +using namespace std; + +const std::set my_operators{ + "+", "+-+", "-", "*", "/", "%", "^", "=", "==", "(", ")", "?", "£", "$", "####" + }; + +class Token_Private_Tester +{ +public: + Token_Private_Tester(Token& t) : t{t} {} + + bool is_delimeter(int c) const { return t.is_delimeter(c); } + bool is_separator(int c) const { return t.is_separator(c); } + + bool is_candidate() const { return t.is_candidate(); } + + bool check_candidate(string const& s) { t.token = s; return t.is_candidate(); } + + Token& set(string const& s) { t.token = s; return t; } + +private: + Token& t; +}; + +TEST_CASE("help functions") +{ + Token tok{my_operators}; + Token_Private_Tester t{tok}; + + CHECK( t.is_delimeter('+') ); + CHECK( t.is_delimeter('#') ); + CHECK( t.is_delimeter(' ') ); + CHECK_FALSE( t.is_delimeter('.') ); + + CHECK( t.is_separator(' ') ); + CHECK_FALSE( t.is_separator('0') ); + + CHECK( t.check_candidate("+") ); + CHECK( t.check_candidate("+-") ); + CHECK_FALSE( t.check_candidate("+-+") ); + CHECK_FALSE( t.check_candidate("+-++") ); + +} + +TEST_CASE("classifier functions") +{ + Token tok{my_operators}; + Token_Private_Tester t{tok}; + + CHECK( t.set("+").is_operator() ); + CHECK_FALSE( t.set("+-").is_operator() ); + CHECK( t.set("+-+").is_operator() ); + CHECK_FALSE( t.set("+-++").is_operator() ); + + CHECK( t.set("123").is_integer() ); + CHECK( t.set("3.14").is_decimal() ); + CHECK( t.set("x_34").is_identifier() ); + + CHECK_FALSE( t.set("123a").is_integer() ); + CHECK_FALSE( t.set("3.14.").is_decimal() ); + CHECK_FALSE( t.set("=x_34").is_identifier() ); +} + +TEST_CASE("normal input output") +{ + Token t{my_operators}; + istringstream iss{"1+2*34-sfd"}; + ostringstream oss{}; + + while ( iss >> t ) + { + oss << t << " "; + } + CHECK( oss.str() == "1 + 2 * 34 - sfd "); +} + +TEST_CASE("normal input output, default operators") +{ + Token t; + istringstream iss{"1+2*34-sfd"}; + ostringstream oss{}; + + while ( iss >> t ) + { + oss << t << " "; + } + CHECK( oss.str() == "1 + 2 * 34 - sfd "); +} + +TEST_CASE("multichar operator input output") +{ + Token t{my_operators}; + istringstream iss{"1+-++2===as#####fgh"}; + ostringstream oss{}; + + while ( iss >> t ) + { + oss << t << " "; + } + CHECK( oss.str() == "1 +-+ + 2 == = as #### #fgh "); +} + +int main(int argc, char* argv[] __attribute__((unused))) +{ + Catch::Session session; + + session.run(); + + + Token t{my_operators}; + string s; + + if ( argc <= 1 ) + return 0; + + cout << "Manual test mode, press Ctrl-D to exit. " + << "Please enter lines to split: " << endl; + while ( getline(cin, s) ) + { + istringstream iss{s}; + + while ( iss >> t ) + { + if ( t.is_operator() ) + cout << "op: '" << t << "', "; + else if ( t.is_integer() ) + cout << "int: '" << t << "', "; + else if ( t.is_decimal() ) + cout << "double: '" << t << "', "; + else if ( t.is_identifier() ) + cout << "var: '" << t << "', "; + else + cout << "token: '" << t << "', "; + } + cout << endl; + } + return 0; +} diff --git a/src/uppgift13.cc b/src/uppgift13.cc new file mode 100644 index 0000000..fb82a08 --- /dev/null +++ b/src/uppgift13.cc @@ -0,0 +1,15 @@ +#include + +using namespace std; + +int main() +{ + string line; + while ( getline(cin, line) ) + { + Expression e{line}; + cout << e.to_string() << endl + << e.evaluate() << endl; + } + return 0; +} -- 2.30.2