Author: cpptutor

Last time we developed a program that converted infix expressions with positive numbers to postfix, supporting the addition, subtraction, multiplication and division operators. We’re going to finish this program so that it handles unary-minus (therefore negative numbers), exponentiation and parentheses, as well as actually performing the evaluation through a new class called StackCalculator, inherited from our existing StackMachine. Small parts of example code follow, which indicate additions to the previous version, and the complete, new, working program is listed at the end of this article.

Most Mathematicians write expressions using infix notation, where the precedence and associativity of each operator is implied by standard math conventions. (Thus 1+2×3 is 7, not 9.) In 1924 the Polish logician Jan Łukasiewicz postulated prefix notation, which he called “Polish Notation”. A possible application of Polish Notation is translating expressions as named function calls (assuming suitably-named functions are available), such as: sum(1, product(2, 3)). However this isn’t particularly useful as function call overhead would in practice make this method of evaluation inefficient.

Around the time of the first Fortran compiler, the application of postfix notation was explored, which was named Reverse Polish Notation (RPN). In this form, the operators are written after the operands, thus: 1 2 3 × +. The method for parsing an expression written in Reverse Polish Notation using a Stack Machine is as follows:

C++ inherits its string-literal syntax from C, that is any number of characters enclosed between double quotes is copied verbatim to the generated executable (with a trailing NUL-byte added automatically). A pointer to the first character is what the compiler assigns to any “string” variable; this points to a read-only part of the running program.

auto s1 = "abracadabra!"; // s1 is actually of type: const char *

To get write access to this string, a C-style array can be used; this also allows use of the begin()/end() family of function templates, so your “string” is now compatible with range-for.

Obtaining a floating-point or integral value from a string is so often necessary that there are more than one ways of doing this due to the history of C++ (and C). Before we look at the most modern (and best!) let’s consider all of the ways that modern C++ has inherited or developed for performing this task:

1 – atoi, atof

These are C-library functions which accept a pointer to a null-terminated multi-byte string (NTMBS) and return an integral or floating-point type. Any trailing non-numeric characters are ignored, as is preceding and trailing whitespace. Invalid input causes a zero-value number to be returned.

So we all know that a prime number has only two factors, being one and itself? A first attempt at writing a function to tell if a given number is prime might look like this:

constexpr bool isPrime(int n) {
    for (int i = 2; (i * i) < n; ++i) {
        if (!(n % i)) {
            return false;
        }
    }
    return true;
}

The structure is straightforward, we loop over the semi-open range [2,√n) and break on the first occurrence (if any) of the loop counter being a factor of n.

In this final mini-series article we’ll cover using flex to generate a C++ scanner, and use this with a slightly modified version of our previous bison C++ parser program. A number of changes need to be made to both of the source files, as well as there being two new header dependencies, making for three header files in total (we don’t want to ask flex to create a header, this time). The first of these new headers is called FlexLexer.h and is distributed with the flex program in $PREFIX/include where $PREFIX is where flex was installed, such as /usr/local/. (Under Windows this file is probably in the same directory as win_flex.exe.) This header defines an abstract base class (ABC) FlexLexer from which the implementation class (snappily named yyFlexLexer) derives.

In this second article we’ll get straight on with generating the C++ parser using bison. The source code is about twice the length of the scanner and is more complex in implementation, and it would be impossible to explain every part from scratch in one article. The main parts of the configuration to instruct bison to use a C++ parser class are covered. Interestingly the overall format is similar to flex‘s input file, being three sections separated by %% on a line by itself. Here is the bison input file grammar1.y:

This mini-series of articles describes the use of GNU flex and bison when C++ output is desired, which has been possible for some time. The flex utility is a scanner generator while bison is a parser generator; each utility outputs compilable source code from a user-defined input file containing configuration options, syntax specific to the utility, and C++ code fragments. Simply put, the (generated) parser program is meant to call the (generated) scanner repeatedly; the scanner translates its input into a sequence of tokens, each with an optional semantic value. The parser checks this token stream for valid grammatically correct sequences, which causes it to perform actions using the semantic values. Invalid sequences trigger a “syntax error” within the parser.

Despite the fact that it is possible to create C++ scanner and parser classes with flex and bison, much online advice seems to suggest merely creating a C scanner and/or C parser, and then compiling this output with a C++ compiler in order to be able to use (unions with fields of) std::string* etc. for semantic types. However this first article describes the use of flex in its C generation mode with bison generating C++. (If you really want to know how to interface a C++ bison class with a C++ flex class straightaway, then skip to part 3, which also has links to downloads of the resources used. However the reason I cover this later is because it involves creation of a supplementary custom-written header file, and is a less “clean” method in my view.)

In this fourth and final article of this mini-series we’re going to look at replicating the JSON container program from part three using variant instead of any. As previously mentioned variant is essentially a type-safe union with an additional discriminant field, which means that extracting the correct type is less problematic than for any. Essentially, it is possible to switch on the index() member function, which returns the index of the type that the variant object holds, instead of requiring chained if-else-if statements.

As promised, in this article we’re going to look at using any to store a representation of an arbitrary JSON object. In case you didn’t already know, JSON stands for “JavaScript Object Notation” and is easy to parse both for humans and machines (compared to XML, for example). A JSON object is essentially an array of key names followed by a colon followed by the value, separated by commas and surrounded by curly braces. So already we can name our container type for JSON:

using JSON = vector<pair<string,any>>;

Last time we looked at how to assign a value to an object of type any or variant. In this article we’re going to look at how to extract this value in order to output it or assign it to another variable (of known type). We’ll also consider how to use any and variant with streams.

These two C++ types have a few things in common: they are both new additions to the C++17 Standard (requiring compiler support, so they are not back-portable), they allow initialization and (re-)assignment from different types (that is, they are in some ways true polymorphic types), and they can both throw exceptions when dereferenced incorrectly.

But they are very different under the hood. This article aims to be one of a planned mini-series covering how these two types are used so that, hopefully, you will know which, if either, to use.

It’s often interesting to see just how much can be accomplished with just one line of code; this mini-article has been written to demonstrate a solution to an age-old problem: How to convert *argv[] into something usable in (Modern) C++.

Any seasoned C programmer will be quick to tell you there are two forms to the main() function, the empty parentheses variant and the one specifying argc (number of arguments) and argv (a pointer to an array of pointer to char).

If your head hurts if you try to determine whether there’s any difference to declaring argv as const char **argv or const char *argv[] you’re probably not alone. (No, there isn’t a difference, is the answer.) In Modern C++ we hardly want to be messing around with a single const char * if we can help it, never mind an array of them. So, how to construct and populate a vector of string views in one line? Here is the code (line 12 is the one-line magic):

This article aims to summarize the current status as regards Modules and the import keyword with modern compilers, in particular accessing the Standard Library without the need for #include <iostream> and similar.

At the time of writing, two of the most popular C++ compilers (Visual Studio 2022 and Clang) offer full support for modules including importing the Standard Library as a module, while GCC g++ offers some support for writing modules, as detailed below:

It’s difficult to imagine even a simple program which doesn’t use something from the std namespace, so most C++ programmers are introduced to namespaces early on. Namespaces use the same double-colon syntax as static members of structs and classes, so sometimes it’s not clear to user code which is which. Consider the following code fragment: