enum class TokenType { Null, Operator, Operand, LBracket, RBracket };

enum class OperatorType { NullOp, AddOp, SubOp, MulOp, DivOp, ModOp };

Token tok1{ TokenType::LBracket };
Token tok2{ TokenType::RBracket };
Token tok3{ TokenType::Operator, OperatorType::AddOp };
Token tok4{ TokenType::Operand, 12345 };

std::cout << tok1 << std::endl;
std::cout << tok2 << std::endl;
std::cout << tok3 << std::endl;
std::cout << tok4 << std::endl;

Scanner scanner;
scanner.set("1 2 *");
std::cout << scanner << std::endl;

Scanner<int> scanner;
scanner.set("1 2 - 3 -");
scanner.scan();
for (const auto& token : scanner) {
    std::cout << "Token: " << token << std::endl;
}

// postfix: 1 2 - 3 - (infix: 1 - 2 - 3)
Token<long long> t1{ 1 };
Token<long long> t2{ 2 };
Token<long long> t3{ OperatorType::SubOp };
Token<long long> t4{ 3 };
Token<long long> t5{ OperatorType::SubOp };

std::list<Token<long long>> tokens;
tokens.push_back(t1);
tokens.push_back(t2);
tokens.push_back(t3);
tokens.push_back(t4);
tokens.push_back(t5);

// print postfix notation to stdout
std::cout << "Postfix Expression: " << std::endl;
for (const auto& token : tokens) {
    std::cout << token << ' ';
}
std::cout << std::endl;

// calculate result of postfix expression
PostfixCalculator<long long> calculator;
auto result = calculator.calc(std::begin(tokens), std::end(tokens));
std::cout << "Result: " << result << std::endl;

// sum of first ten numbers
Scanner<int> scanner;
scanner.set("0 1 2 3 4 5 6 7 8 9 + + + + + + + + +");
scanner.scan_classic();

PostfixCalculator<int> calculator;
int result = calculator.calc(scanner.begin(), scanner.end());
std::cout << "Result: " << result << std::endl;

constexpr size_t MaxPower = 16;

for (size_t n{1}; n != MaxPower; ++n) {

    // construct scan string for powers of '2'
    std::string s{};
    for (size_t i{}; i != n; ++i) {
        s.append("2 ");
    }
    for (size_t i{}; i != n - 1; ++i) {
        s.append("* ");
    }

    // compute value
    Scanner<int> scanner;
    scanner.set(s);
    scanner.scan();

    PostfixCalculator<int> calculator;
    int result = calculator.calc(scanner.begin(), scanner.end());
    std::cout << scanner.get() << " ==> " << result << std::endl;
}

Scanner<int> scanner;
scanner.set("2 * 3 / (2 - 1) + 5 * (4 - 1)");
scanner.scan();

// print postfix notation to stdout
std::cout << "Infix Expression:   ";
for (const Token<int>& token : scanner) {
    std::cout << token << ' ';
}
std::cout << std::endl << std::endl;

InfixToPostfixConverter<int> conv;
std::list<Token<int>> postfix = conv.convert(std::begin(scanner), std::end(scanner));

// print postfix notation to stdout
std::cout << "Postfix Expression: ";
for (const Token<int>& token : postfix) {
    std::cout << token << ' ';
}
std::cout << std::endl;

PostfixCalculator<int> calculator;
int result = calculator.calc(std::begin(postfix), std::end(postfix));
std::cout << "Result: " << result << std::endl;

001: enum class TokenType { Null, Operator, Operand, LBracket, RBracket };
002: 
003: enum class OperatorType { NullOp, AddOp, SubOp, MulOp, DivOp, ModOp };
004: 
005: template <typename T>
006: class Token;
007: 
008: template <typename T>
009: std::ostream& operator<< (std::ostream&, const Token<T>&);
010: 
011: template <typename T>
012: class Token
013: {
014:     friend std::ostream& operator<< <> (std::ostream&, const Token<T>&);
015: 
016: private:
017:     // member data
018:     TokenType m_type;      // classification of token
019:     OperatorType m_op;     // classification of operator (TokenType == Operator)
020:     T m_value;             // value of constant (TokenType == Constant)
021:     size_t m_precedence;   // precedence of this operator, if any 
022: 
023: public:
024:     // c'tor(s)
025:     Token() : Token(TokenType::Null, OperatorType::NullOp, T{}) {}
026:     Token(TokenType type) : Token(type, OperatorType::NullOp, T{}) {}
027:     Token(OperatorType op) : Token(TokenType::Operator, op, T{}) {}
028:     Token(T value) : Token(TokenType::Operand, OperatorType::NullOp, value) {}
029: 
030:     // getter
031:     TokenType getTokenType() const { return m_type; }
032:     OperatorType getOperatorType() const { return m_op; }
033:     T getValue() const { return m_value; }
034:     size_t getPrecedence() const { return m_precedence; }
035: 
036: private:
037:     // general purpose c'tor
038:     Token(TokenType type, OperatorType op, T value) 
039:         : m_type{ type }, m_op{ op }, m_value{ value } 
040:     {
041:         switch (op)
042:         {
043:         case OperatorType::AddOp:
044:         case OperatorType::SubOp:
045:             m_precedence = 1;
046:             break;
047:         case OperatorType::MulOp:
048:         case OperatorType::DivOp:
049:         case OperatorType::ModOp:
050:             m_precedence = 2;
051:             break;
052:         default:
053:             m_precedence = 0;
054:         }
055:     }
056: };
057: 
058: template <typename T>
059: std::ostream& operator<< (std::ostream& os, const Token<T>& tok)
060: {
061:     switch (tok.m_type)
062:     {
063:     case TokenType::Operand:
064:         os << tok.m_value;
065:         break;
066: 
067:     case TokenType::Operator:
068:         switch (tok.m_op)
069:         {
070:         case OperatorType::AddOp:
071:             os << '+';
072:             break;
073:         case OperatorType::SubOp:
074:             os << '-';
075:             break;
076:         case OperatorType::MulOp:
077:             os << '*';
078:             break;
079:         case OperatorType::DivOp:
080:             os << '/';
081:             break;
082:         case OperatorType::ModOp:
083:             os << '%';
084:             break;
085:         case OperatorType::NullOp:
086:             break;
087:         }
088:         break;
089: 
090:     case TokenType::LBracket:
091:         os << '(';
092:         break;
093: 
094:     case TokenType::RBracket:
095:         os << ')';
096:         break;
097: 
098:     default:
099:         os << ' ';  // suited for debugging output
100:         break;
101:     }
102: 
103:     return os;
104: }

001: template <typename T>
002: class Scanner
003: {
004: private:
005:     const std::string token_regex = "([0]|[1-9][0-9]*)|[(]|[)]|\\+|\\-|\\*|\\/|\\%";
006: 
007: public:
008:     using iterator = std::list<Token<T>>::iterator;
009:     using const_iterator = std::list<Token<T>>::const_iterator;
010: 
011: private:
012:     std::string         m_line;
013:     std::list<Token<T>> m_tokens;
014:     std::regex          m_token_regex;
015: 
016: public:
017:     // c'tor
018:     Scanner() : m_line{}, m_token_regex{ token_regex } {}
019:      
020:     // getter/setter
021:     void set(const std::string& line) { m_line = line; }
022:     const std::string& get() const { return m_line; }
023: 
024:     // iterator support
025:     iterator begin() { return m_tokens.begin(); }
026:     iterator end() { return m_tokens.end(); }
027:     const_iterator begin() const { return m_tokens.cbegin(); }
028:     const_iterator end() const { return m_tokens.cend(); }
029: 
030:     // public interface
031:     void scan()
032:     {
033:         m_tokens.clear();
034: 
035:         auto rbegin = std::sregex_iterator(
036:             std::begin(m_line),
037:             std::end(m_line),
038:             m_token_regex
039:         );
040: 
041:         auto rend = std::sregex_iterator();
042: 
043:         while (rbegin != rend)
044:         {
045:             std::smatch m = *rbegin;
046:             std::string token = m.str();
047: 
048:             Token<T> tok{};
049:             switch (token[0])
050:             {
051:             case '(':
052:                 tok = Token<T>{ TokenType::LBracket };
053:                 m_tokens.push_back(tok);
054:                 break;
055: 
056:             case ')':
057:                 tok = Token<T>{ TokenType::RBracket };
058:                 m_tokens.push_back(tok);
059:                 break;
060: 
061:             case '+':
062:                 tok = Token<T>{ OperatorType::AddOp };
063:                 m_tokens.push_back(tok);
064:                 break;
065: 
066:             case '-':
067:                 tok = Token<T>{ OperatorType::SubOp };
068:                 m_tokens.push_back(tok);
069:                 break;
070: 
071:             case '*':
072:                 tok = Token<T>{ OperatorType::MulOp };
073:                 m_tokens.push_back(tok);
074:                 break;
075: 
076:             case '/':
077:                 tok = Token<T>{ OperatorType::DivOp };
078:                 m_tokens.push_back(tok);
079:                 break;
080: 
081:             case '%':
082:                 tok = Token<T>{ OperatorType::ModOp };
083:                 m_tokens.push_back(tok);
084:                 break;
085: 
086:             case '0':
087:             case '1':
088:             case '2':
089:             case '3':
090:             case '4':
091:             case '5':
092:             case '6':
093:             case '7':
094:             case '8':
095:             case '9':
096:             {
097:                 long long tmp{ stoll(token) };
098:                 T value{ static_cast<T>(tmp) };
099:                 tok = Token<T>{ value };
100:                 m_tokens.push_back(tok);
101:                 break;
102:             }
103:             default:
104:                 m_tokens.push_back(tok);
105:                 break;
106:             }
107: 
108:             ++rbegin;
109:         }
110:     }
111: 
112:     void scan_classic() 
113:     {
114:         m_tokens.clear();
115: 
116:         for (size_t i{}; i != m_line.size(); ++i)
117:         {
118:             char ch{ m_line[i] };
119:             Token<T> tok{};
120: 
121:             switch (ch)
122:             {
123:             case ' ':
124:                 continue;
125: 
126:             case '(':
127:                 tok = Token<T>{ TokenType::LBracket };
128:                 m_tokens.push_back(tok);
129:                 break;
130: 
131:             case ')':
132:                 tok = Token<T>{ TokenType::RBracket };
133:                 m_tokens.push_back(tok);
134:                 break;
135: 
136:             case '+':
137:                 tok = Token<T>{ OperatorType::AddOp };
138:                 m_tokens.push_back(tok);
139:                 break;
140: 
141:             case '-':
142:                 tok = Token<T>{ OperatorType::SubOp };
143:                 m_tokens.push_back(tok);
144:                 break;
145: 
146:             case '*':
147:                 tok = Token<T>{ OperatorType::MulOp };
148:                 m_tokens.push_back(tok);
149:                 break;
150: 
151:             case '/':
152:                 tok = Token<T>{ OperatorType::DivOp };
153:                 m_tokens.push_back(tok);
154:                 break;
155: 
156:             case '%':
157:                 tok = Token<T>{ OperatorType::ModOp };
158:                 m_tokens.push_back(tok);
159:                 break;
160: 
161:             case '0':
162:             case '1':
163:             case '2':
164:             case '3':
165:             case '4':
166:             case '5':
167:             case '6':
168:             case '7':
169:             case '8':
170:             case '9':
171:             { 
172:                 T value{};
173:                 while (i != m_line.size() && std::isdigit(m_line[i]))
174:                 {
175:                     value = 10 * value + (m_line[i] - '0');
176:                     ++i;
177:                 }
178: 
179:                 // adjust index
180:                 i--;
181: 
182:                 tok = Token<T>{ value };
183:                 m_tokens.push_back(tok);
184:                 break;
185:             }
186: 
187:             default:
188:                 m_tokens.push_back(tok);
189:             }
190:         }
191:     }
192: };

01: template <typename T>
02: class PostfixCalculator
03: {
04: private:
05:     std::stack<Token<T>> m_stack;  // temporary stack of operands
06: 
07: public:
08:     // public interface
09:     template <typename Iter>
10:     T calc(Iter begin, Iter end)
11:     {
12:         std::stack<Token<T>> m_stack;  // temporary stack of operands
13: 
14:         for (Iter it{ begin }; it != end; ++it)
15:         {
16:             Token<T> tok{ *it };
17: 
18:             if (tok.getTokenType() == TokenType::Operand)
19:             {
20:                 // push operand on temporary operand stack
21:                 m_stack.push(tok);
22:             }
23:             else if (tok.getTokenType() == TokenType::Operator)
24:             {
25:                 // binary operator, retrieve operands from operand stack
26:                 Token<T> right{ m_stack.top() };
27:                 m_stack.pop();
28: 
29:                 Token<T> left{ m_stack.top() };
30:                 m_stack.pop();
31: 
32:                 T rightValue{ right.getValue() };
33:                 T leftValue{ left.getValue() };
34:                 T result{};
35: 
36:                 OperatorType op{ tok.getOperatorType() };
37:                 switch (op)
38:                 {
39:                 case OperatorType::AddOp:
40:                     result = leftValue + rightValue;
41:                     break;
42:                 case OperatorType::SubOp:
43:                     result = leftValue - rightValue;
44:                     break;
45:                 case OperatorType::MulOp:
46:                     result = leftValue * rightValue;
47:                     break;
48:                 case OperatorType::DivOp:
49:                     result = leftValue / rightValue;
50:                     break;
51:                 case OperatorType::ModOp:
52:                     static_assert (
53:                         std::is_integral<T>::value or std::is_floating_point<T>::value,
54:                         "Expected integral or floating-point type."
55:                     );
56:                     if constexpr (std::is_integral<T>::value) {
57:                         result = leftValue % rightValue;
58:                     }
59:                     else if constexpr (std::is_floating_point<T>::value) {
60:                         result = std::fmod(leftValue, rightValue);
61:                     }
62:                     break;
63:                 default:
64:                     break;
65:                 }
66: 
67:                 // push result to operand stack
68:                 Token<T> val{ result };
69:                 m_stack.push(val);
70:             }
71:         }
72: 
73:         // retrieve result from stack
74:         Token<T> result{ m_stack.top() };
75:         m_stack.pop();
76:         return result.getValue();
77:     }
78: };

001: template <typename T>
002: class InfixToPostfixConverter
003: {
004: private:
005:     std::list<Token<T>> m_postfix;     // postfix expression (output)
006:     std::stack<Token<T>> m_stack;      // temporary stack of operators and brackets
007: 
008: public:
009:     // public interface
010:     template <typename Iter>
011:     std::list<Token<T>> convert(Iter begin, Iter end) {
012:         clear();
013: 
014:         Token<T> next{};
015:         if (begin != end) {
016:             next = *begin;
017:             ++begin;
018:         }
019: 
020:         while (next.getTokenType() != TokenType::Null)
021:         {
022:             if (next.getTokenType() == TokenType::Operand)
023:                 processOperand(next);
024:             else if (next.getTokenType() == TokenType::Operator)
025:                 processOperator(next);
026:             else if (next.getTokenType() == TokenType::LBracket)
027:                 processLeftParenthesis(next);
028:             else if (next.getTokenType() == TokenType::RBracket)
029:                 processRightParenthesis();
030: 
031:             dumpStacks(next);
032: 
033:             if (begin != end) {
034:                 next = *begin;
035:                 ++begin;
036:             }
037:             else {
038:                 next = {};
039:             }
040:         }
041: 
042:         processEndOfInput();
043:         dumpStacks(next);
044: 
045:         return m_postfix;
046:     }
047: 
048: private:
049:     // helper methods
050:     void clear() {
051:         m_postfix.clear();
052:     }
053: 
054:     void processOperand(Token<T> next) {
055:         // append operand to the postfix buffer
056:         m_postfix.push_back(next);
057:     }
058: 
059:     void processOperator(Token<T> next) {
060:         /**
061:          * Move operators from the stack to the output buffer, as long as
062:          * - the incoming operator precedence is lower or equal to a stacked operator,
063:          * - no left parenthesis appears on the stack
064:          * - and the stack is not empty.
065:          * The incoming operator is stacked.
066:          */
067:         do
068:         {
069:             if (m_stack.empty())
070:                 break;
071: 
072:             // left parenthesis on stack encountered
073:             Token<T> top = m_stack.top();
074:             if (top.getTokenType() == TokenType::LBracket)
075:                 break;
076: 
077:             if (next.getPrecedence() <= top.getPrecedence())
078:             {
079:                 m_stack.pop();
080:                 m_postfix.push_back(top);
081:             }
082:             else {
083:                 break;
084:             }
085:         } while (true);
086: 
087:         // stack incoming operator
088:         m_stack.push(next);
089:     }
090: 
091:     void processLeftParenthesis(Token<T> next) {
092:         // push a left parenthesis onto the operator stack
093:         m_stack.push(next);
094:     }
095: 
096:     void processRightParenthesis()
097:     {
098:         // move operators from the stack to the output buffer, until a left 
099:         // parenthesis appears on the stack (the left parenthesis is discarded)
100:         do
101:         {
102:             Token<T> top = m_stack.top();
103: 
104:             if (top.getTokenType() == TokenType::LBracket)
105:                 break;
106: 
107:             m_stack.pop();
108:             m_postfix.push_back(top);
109:         } while (true);
110: 
111:         // discard left parenthesis
112:         m_stack.pop();
113:     }
114: 
115:     void processEndOfInput() {
116:         // copy remaining elements from operator stack to postfix buffer
117:         while (!m_stack.empty())
118:         {
119:             Token<T> top = m_stack.top();
120:             m_stack.pop();
121:             m_postfix.push_back(top);
122:         }
123:     }
124: 
125:     void dumpStacks(Token<T> next) {
126:         // dump latest token
127:         std::cout << next << "  ";
128: 
129:         // output stack (not trivial, because stack has limited iterator support)
130:         std::cout << "[";
131:         if (m_stack.size() != 0) {
132:             // need a copy of the stack
133:             std::stack<Token<T>> stack{ m_stack };
134:             std::vector<Token<T>> tmp{};
135:             while (!stack.empty()) {
136:                 Token<T> top = stack.top();
137:                 stack.pop();
138:                 tmp.push_back(top);
139:             }
140: 
141:             std::reverse(
142:                 std::begin(tmp),
143:                 std::end(tmp)
144:             );
145: 
146:             std::for_each(
147:                 std::begin(tmp),
148:                 std::prev(std::end(tmp)),
149:                 [](const Token<T>& token) {
150:                     std::cout << token << ", ";
151:                 }
152:             );
153: 
154:             const Token<T>& latest = tmp.back();
155:             std::cout << latest;
156:         }
157:         std::cout << "]";
158: 
159:         // fill gap equally spaced
160:         const size_t MaxDistance = 20;
161:         size_t size = m_stack.size();
162:         size_t count{};
163: 
164:         if (size == 0) {
165:             count = MaxDistance - 2;
166:         }
167:         else if (size == 1) {
168:             count = MaxDistance - 3;
169:         }
170:         else {
171:             count = MaxDistance - (3 * size);
172:         }
173: 
174:         for (size_t n{}; n != count; ++n) {
175:             std::cout << " ";
176:         }
177: 
178:         // output so far calculated tokens in postfix order
179:         std::cout << '[';
180:         if (m_postfix.size() != 0) {
181: 
182:             std::for_each(
183:                 std::begin(m_postfix),
184:                 std::prev(std::end(m_postfix)),
185:                 [](const Token<T>& token) {
186:                     std::cout << token << ", ";
187:                 }
188:             );
189: 
190:             const Token<T>& latest = m_postfix.back();
191:             std::cout << latest;
192:         }
193: 
194:         std::cout << ']';
195:         std::cout << std::endl;
196:     }
197: };

int getValue() const;