C++ Programming Code Examples
C++ > Computer Graphics Code Examples
Program to Construct an Expression Tree for an Infix Expression
/* Program to Construct an Expression Tree for an Infix Expression
This is a C++ Program to construct an Expression tree for an Infix Expression. A binary expression tree is a specific application of a binary tree to evaluate certain expressions. Two common types of expressions that a binary expression tree can represent are algebraic[1] and boolean. These trees can represent expressions that contain both unary and binary operators.In general, expression trees are a special kind of binary tree. A binary tree is a tree in which all nodes contain zero, one or two children. This restricted structure simplifies the programmatic processing of Expression trees */
#include <cstdlib>
#include <iostream>
#include <sstream>
#include <string>
#include <stack>
#include <exception>
using namespace std;
class ExpressionElementNode
{
public:
virtual double value() = 0; // Return the value of this node.
};
class NumericElementNode: public ExpressionElementNode
{
private:
double number;
NumericElementNode(const NumericElementNode& n);
NumericElementNode();
NumericElementNode&operator=(const NumericElementNode& n);
public:
NumericElementNode(double val);
virtual double value();
};
inline NumericElementNode::NumericElementNode(double val) :
number(val)
{
}
inline double NumericElementNode::value()
{
return number;
}
class BinaryOperationNode: public ExpressionElementNode
{
private:
char binary_op;
ExpressionElementNode *left;
ExpressionElementNode *right;
BinaryOperationNode(const BinaryOperationNode& n);
BinaryOperationNode();
BinaryOperationNode &operator=(const BinaryOperationNode& n);
public:
BinaryOperationNode(char op, ExpressionElementNode *l,
ExpressionElementNode *r);
virtual double value();
};
inline BinaryOperationNode::BinaryOperationNode(char op,
ExpressionElementNode *l, ExpressionElementNode *r) :
binary_op(op), left(l), right(r)
{
}
double BinaryOperationNode::value()
{
// To get the value, compute the value of the left and
// right operands, and combine them with the operator.
double leftVal = left->value();
double rightVal = right->value();
double result;
switch (binary_op)
{
case '+':
result = leftVal + rightVal;
break;
case '-':
result = leftVal - rightVal;
break;
case '*':
result = leftVal * rightVal;
break;
case '/':
result = leftVal / rightVal;
break;
}
return result;
}
class ExpressionElementNode;
class BinaryOperationNode;
class BinaryExpressionBuilder
{
private:
// holds either (, +, -, /, or *
std::stack<char> operatorStack;
// operandStack is made up of BinaryOperationNodes and NumericElementNode
std::stack<ExpressionElementNode *> operandStack;
void processOperator(char op);
void processRightParenthesis();
void doBinary(char op);
int precedence(char op);
public:
class NotWellFormed: public std::exception
{
public:
virtual const char* what() const throw ()
{
return "The expression is not valid";
}
};
BinaryOperationNode *parse(std::string& istr) throw (NotWellFormed);
};
int BinaryExpressionBuilder::precedence(char op)
{
enum
{
lowest, mid, highest
};
switch (op)
{
case '+':
case '-':
return mid;
case '/':
case '*':
return highest;
default:
return lowest;
}
}
// Input: +, -, /, or *
// creates BinaryOperationNode's from all preceding
BinaryOperationNode *BinaryExpressionBuilder::parse(std::string& str)
throw (NotWellFormed)
{
istringstream istr(str);
char token;
while (istr >> token)
{
switch (token)
{
case '+':
case '-':
case '*':
case '/':
processOperator(token);
break;
case ')':
processRightParenthesis();
break;
case '(':
operatorStack.push(token);
break;
default:
// If it is not an operator, it must be a number.
// Since token is only a char in width, we put it back,
// and get the complete number as a double.
istr.putback(token);
double number;
istr >> number;
NumericElementNode *newNode = new NumericElementNode(number);
operandStack.push(newNode);
continue;
} // end switch
} // end while
while (!operatorStack.empty())
{
doBinary(operatorStack.top());
operatorStack.pop();
}
// Invariant: At this point the operandStack should have only one element
// operandStack.size() == 1
// otherwise, the expression is not well formed.
if (operandStack.size() != 1)
{
throw NotWellFormed();
}
ExpressionElementNode *p = operandStack.top();
return static_cast<BinaryOperationNode *> (p);
}
void BinaryExpressionBuilder::processOperator(char op)
{
// pop operators with higher precedence and create their BinaryOperationNode
int opPrecedence = precedence(op);
while ((!operatorStack.empty()) && (opPrecedence <= precedence(
operatorStack.top())))
{
doBinary(operatorStack.top());
operatorStack.pop();
}
// lastly push the operator passed onto the operatorStack
operatorStack.push(op);
}
void BinaryExpressionBuilder::processRightParenthesis()
{
while (!operatorStack.empty() && operatorStack.top() != '(')
{
doBinary(operatorStack.top());
operatorStack.pop();
}
operatorStack.pop(); // remove '('
}
// Creates a BinaryOperationNode from the top two operands on operandStack
// These top two operands are removed (poped), and the new BinaryOperation
// takes their place on the top of the stack.
void BinaryExpressionBuilder::doBinary(char op)
{
ExpressionElementNode *right = operandStack.top();
operandStack.pop();
ExpressionElementNode *left = operandStack.top();
operandStack.pop();
BinaryOperationNode *p = new BinaryOperationNode(operatorStack.top(), left,
right);
operandStack.push(p);
}
int main(int argc, char** argv)
{
NumericElementNode num1(10);
NumericElementNode num2(20);
BinaryOperationNode n('+', &num1, &num2);
BinaryExpressionBuilder b;
cout << "Enter expression" << endl;
string expression;
getline(cin, expression);
BinaryOperationNode *root = b.parse(expression);
cout << " result = " << root->value();
return 0;
}
Continue statement is used inside loops. Whenever a continue statement is encountered inside a loop, control directly jumps to the beginning of the loop for next iteration, skipping the execution of statements inside loop's body for the current iteration. The continue statement works somewhat like the break statement. Instead of forcing termination, however, continue forces the next iteration of the loop to take place, skipping any code in between. For the for loop, continue causes the conditional test and increment portions of the loop to execute. For the while and do...while loops, program control passes to the conditional tests.
Static Cast: This is the simplest type of cast which can be used. It is a compile time cast.It does things like implicit conversions between types (such as int to float, or pointer to void*), and it can also call explicit conversion functions (or implicit ones). The static_cast is used for the normal/ordinary type conversion. This is also the cast responsible for implicit type coercion and can also be called explicitly. You should use it in cases like converting float to int, char to int, etc. This can cast related type classes. If you want to perform any type of conversion that is based on compile-time (static) inference, this is the way to go. We can do the common C-type casting using static_cast(), such as converting an int to a float, and vice-versa. Similarly, we can also convert between pointers and references.
#include is a way of including a standard or user-defined file in the program and is mostly written at the beginning of any C/C++ program. This directive is read by the preprocessor and orders it to insert the content of a user-defined or system header file into the following program. These files are mainly imported from an outside source into the current program. The process of importing such files that might be system-defined or user-defined is known as File Inclusion. This type of preprocessor directive tells the compiler to include a file in the source code program.
Get string identifying exception. Returns a null terminated character sequence that may be used to identify the exception. The particular representation pointed by the returned value is implementation-defined. As a virtual function, derived classes may redefine this function so that specific values are returned. The exception::what() used to get string identifying exception. This function returns a null terminated character sequence that may be used to identify the exception. Below is the syntax for the same: This function does not accept any parameter. Function returns a pointer to a c-string with content related to the exception.
In C++, classes and structs are blueprints that are used to create the instance of a class. Structs are used for lightweight objects such as Rectangle, color, Point, etc. Unlike class, structs in C++ are value type than reference type. It is useful if you have data that is not intended to be modified after creation of struct. C++ Structure is a collection of different data types. It is similar to the class that holds different types of data. A structure is declared by preceding the struct keyword followed by the identifier(structure name). Inside the curly braces, we can declare the member variables of different types.
The main purpose of C++ programming is to add object orientation to the C programming language and classes are the central feature of C++ that supports object-oriented programming and are often called user-defined types. A class is used to specify the form of an object and it combines data representation and methods for manipulating that data into one neat package. The data and functions within a class are called members of the class.
The stringstream, ostringstream, and istringstream objects are used for input and output to a string. They behave in a manner similar to fstream, ofstream and ifstream objects. The function str() can be used in two ways. First, it can be used to get a copy of the string that is being manipulated by the current stream string. This is most useful with output strings. The first form (1) returns a string object with a copy of the current contents of the stream. The second form (2) sets s as the contents of the stream, discarding any previous contents. The object preserves its open mode: if this includes ios_base::ate, the writing position is moved to the end of the new sequence. Internally, the function calls the str member of its internal string buffer object.
Consider a situation, when we have two persons with the same name, jhon, in the same class. Whenever we need to differentiate them definitely we would have to use some additional information along with their name, like either the area, if they live in different area or their mother's or father's name, etc. Same situation can arise in your C++ applications. For example, you might be writing some code that has a function called xyz() and there is another library available which is also having same function xyz(). Now the compiler has no way of knowing which version of xyz() function you are referring to within your code.
Inline function is one of the important feature of C++. So, let's first understand why inline functions are used and what is the purpose of inline function? When the program executes the function call instruction the CPU stores the memory address of the instruction following the function call, copies the arguments of the function on the stack and finally transfers control to the specified function. The CPU then executes the function code, stores the function return value in a predefined memory location/register and returns control to the calling function. This can become overhead if the execution time of function is less than the switching time from the caller function to called function (callee). For functions that are large and/or perform complex tasks, the overhead of the function call is usually insignificant compared to the amount of time the function takes to run. However, for small, commonly-used functions, the time needed to make the function call is often a lot more than the time needed to actually
A cast is a special operator that forces one data type to be converted into another. As an operator, a cast is unary and has the same precedence as any other unary operator. Converting an expression of a given type into another type is known as type-casting. The most general cast supported by most of the C++ compilers is as follows:
LIFO stack. Stacks are a type of container adaptor, specifically designed to operate in a LIFO context (last-in first-out), where elements are inserted and extracted only from one end of the container. stacks are implemented as container adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements are pushed/popped from the "back" of the specific container, which is known as the top of the stack.
Remove top element. Removes the element on top of the stack, effectively reducing its size by one. The C++ function std::stack::pop() removes top element from the stack and reduces size of stack by one. This function calls destructor on removed element. The element removed is the latest element inserted into the stack, whose value can be retrieved by calling member stack::top. This calls the removed element's destructor. This member function effectively calls the member function pop_back of the underlying container object.
In computer programming, we use the if statement to run a block code only when a certain condition is met. An if statement can be followed by an optional else statement, which executes when the boolean expression is false. There are three forms of if...else statements in C++: • if statement, • if...else statement, • if...else if...else statement, The if statement evaluates the condition inside the parentheses ( ). If the condition evaluates to true, the code inside the body of if is executed. If the condition evaluates to false, the code inside the body of if is skipped.
Put character back. Attempts to decrease the current location in the stream by one character, making the last character extracted from the stream once again available to be extracted by input operations. Internally, the function accesses the input sequence by first constructing a sentry object (with noskipws set to true). Then (if good), it calls sputbackc(c) on its associated stream buffer object (if any). Finally, it destroys the sentry object before returning. Function returns the istream object (*this). The function clears the eofbit flag, if set before the call.
In while loop, condition is evaluated first and if it returns true then the statements inside while loop execute, this happens repeatedly until the condition returns false. When condition returns false, the control comes out of loop and jumps to the next statement in the program after while loop. The important point to note when using while loop is that we need to use increment or decrement statement inside while loop so that the loop variable gets changed on each iteration, and at some point condition returns false. This way we can end the execution of while loop otherwise the loop would execute indefinitely. A while loop that never stops is said to be the infinite while loop, when we give the condition in such a way so that it never returns false, then the loops becomes infinite and repeats itself indefinitely.
Allocate storage space. Default allocation functions (single-object form). A new operator is used to create the object while a delete operator is used to delete the object. When the object is created by using the new operator, then the object will exist until we explicitly use the delete operator to delete the object. Therefore, we can say that the lifetime of the object is not related to the block structure of the program.
Break statement in C++ is a loop control statement defined using the break keyword. It is used to stop the current execution and proceed with the next one. When a compiler calls the break statement, it immediately stops the execution of the loop and transfers the control outside the loop and executes the other statements. In the case of a nested loop, break the statement stops the execution of the inner loop and proceeds with the outer loop. The statement itself says it breaks the loop. When the break statement is called in the program, it immediately terminates the loop and transfers the flow control to the statement mentioned outside the loop.
Get line from stream into string. The cin is an object which is used to take input from the user but does not allow to take the input in multiple lines. To accept the multiple lines, we use the getline() function. It is a pre-defined function defined in a <string.h> header file used to accept a line or a string from the input stream until the delimiting character is encountered. Extracts characters from is and stores them into str until the delimitation character delim is found (or the newline character, '\n', for (2)). The extraction also stops if the end of file is reached in is or if some other error occurs during the input operation. If the delimiter is found, it is extracted and discarded (i.e. it is not stored and the next input operation will begin after it).
Switch statement in C tests the value of a variable and compares it with multiple cases. Once the case match is found, a block of statements associated with that particular case is executed. Each case in a block of a switch has a different name/number which is referred to as an identifier. The value provided by the user is compared with all the cases inside the switch block until the match is found. If a case match is NOT found, then the default statement is executed, and the control goes out of the switch block. • The expression can be integer expression or a character expression. • Value-1, 2, n are case labels which are used to identify each case individually. Remember that case labels should not be same as it may create a problem while executing a program. Suppose we have two cases with the same label as '1'. Then while executing the program, the case that appears first will be executed even though you want the program to execute a second case. This creates problems in the program and
Test whether container is empty. Returns whether the stack is empty: i.e. whether its size is zero. stack::empty() function is an inbuilt function in C++ STL, which is defined in <stack>header file. empty() is used to check whether the associated container is empty or not and return true or false accordingly. This member function effectively calls member empty of the underlying container object. No parameter passed. Function returns true if the underlying container's size is 0, false otherwise.
A C++ virtual function is a member function in the base class that you redefine in a derived class. It is declared using the virtual keyword. It is used to tell the compiler to perform dynamic linkage or late binding on the function. There is a necessity to use the single pointer to refer to all the objects of the different classes. So, we create the pointer to the base class that refers to all the derived objects. But, when base class pointer contains the address of the derived class object, always executes the base class function. This issue can only be resolved by using the 'virtual' function. A 'virtual' is a keyword preceding the normal declaration of a function.
Insert element. Inserts a new element at the top of the stack, above its current top element. The content of this new element is initialized to a copy of val. This member function effectively calls the member function push_back of the underlying container object. C++ Stack push () function is used for adding new elements at the top of the stack. If we have an array of type stack and by using the push() function we can insert new elements in the stack. The elements are inserted at the top of the stack. The element which is inserted most initially is deleted at the end and vice versa as stacks follow LIFO principle.
In C++, constructor is a special method which is invoked automatically at the time of object creation. It is used to initialize the data members of new object generally. The constructor in C++ has the same name as class or structure. Constructors are special class functions which performs initialization of every object. The Compiler calls the Constructor whenever an object is created. Constructors initialize values to object members after storage is allocated to the object. Whereas, Destructor on the other hand is used to destroy the class object. • Default Constructor: A constructor which has no argument is known as default constructor. It is invoked at the time of creating object.
Return size. Returns the number of elements in the stack. stack::size() function is an inbuilt function in C++ STL, which is defined in <stack>header file. size() is used to check the associated container's size and return the result in an integer value, which is the number of elements in the container. If the container is empty the size() returns 0. This member function effectively calls member size of the underlying container object. No parameter is required.
A program shall contain a global function named main, which is the designated start of the program in hosted environment. main() function is the entry point of any C++ program. It is the point at which execution of program is started. When a C++ program is executed, the execution control goes directly to the main() function. Every C++ program have a main() function.
Access next element. Returns a reference to the top element in the stack. stack::top() function is an inbuilt function in C++ STL, which is defined in <stack> header file. top() is used to access the element at the top of the stack container. In a stack, the top element is the element that is inserted at the last or most recently inserted element. Since stacks are last-in first-out containers, the top element is the last element inserted into the stack. This member function effectively calls member back of the underlying container object. No parameter is required.
Examples on different ways to calculate LCM ("Lowest Common Multiple") of two integers using loops and decision making statements. "LCM of two integers" a and b is the smallest
Program should display all 'random elements' of array and minimum and maximum number in array on screen. Array size is fixed to 100 to change the size just change the 'Value of size'
This algorithm generates a undirected graph for the given "Degree Sequence". It does not include self-edge and multiple edges. So this algorithm 'takes the input' of the number of
