1//! @file notation.cpp
2//! @author ryftchen
3//! @brief The definitions (notation) in the algorithm module.
4//! @version 0.1.0
5//! @copyright Copyright (c) 2022-2025 ryftchen. All rights reserved.
6
7#include "notation.hpp"
8
9#include <algorithm>
10#include <stack>
11
12namespace algorithm::notation
13{
14//! @brief Function version number.
15//! @return version number (major.minor.patch)
16const char* version() noexcept
17{
18 static const char* const ver = "0.1.0";
19 return ver;
20}
21
22std::string Notation::prefix(const std::string_view infix)
23{
24 std::string preprocess(infix);
25 std::reverse(first: preprocess.begin(), last: preprocess.end());
26 for (auto& c : preprocess)
27 {
28 if (c == '(')
29 {
30 c = ')';
31 }
32 else if (c == ')')
33 {
34 c = '(';
35 }
36 }
37
38 std::string notation(infixToPostfix(infix: preprocess));
39 std::reverse(first: notation.begin(), last: notation.end());
40 return notation;
41}
42
43std::string Notation::postfix(const std::string_view infix)
44{
45 return infixToPostfix(infix);
46}
47
48std::string Notation::infixToPostfix(const std::string_view infix)
49{
50 std::string postfix{};
51 std::stack<char> charStack{};
52
53 for (const auto c : infix)
54 {
55 if (!isOperator(c))
56 {
57 postfix += c;
58 }
59 else if (c == '(')
60 {
61 charStack.push(x: '(');
62 }
63 else if (c == ')')
64 {
65 while (charStack.top() != '(')
66 {
67 postfix += charStack.top();
68 charStack.pop();
69 }
70 charStack.pop();
71 }
72 else
73 {
74 while (!charStack.empty() && (getPriority(c) <= getPriority(c: charStack.top())))
75 {
76 postfix += charStack.top();
77 charStack.pop();
78 }
79 charStack.push(x: c);
80 }
81 }
82
83 while (!charStack.empty())
84 {
85 postfix += charStack.top();
86 charStack.pop();
87 }
88 return postfix;
89}
90
91Notation::Priority Notation::getPriority(const char c)
92{
93 switch (c)
94 {
95 case '+':
96 [[fallthrough]];
97 case '-':
98 return Priority::low;
99 case '*':
100 [[fallthrough]];
101 case '/':
102 return Priority::medium;
103 case '^':
104 return Priority::high;
105 default:
106 break;
107 }
108 return Priority::none;
109}
110
111bool Notation::isOperator(const char c)
112{
113 return !std::isalpha(c) && !std::isdigit(c);
114}
115} // namespace algorithm::notation
116