This program takes text input and evaluates the expression. This is meant to be an exercise.
I reinvented a stack class though I know C++ provides one in the standard library but it isn"t meant for production use but to solidify my knowledge on linked list data structure
I also made an infix postfix converter which converts 2 + 2 to 22+ which seems easier for a computer to evaluate.
My major concerns are
- Optimization
- Potential pitfalls
- General bad practice
- Readability
- Ease of use
main.cc
#include <iostream>
#include <string>
#include <cassert>
#include <cmath>
#include "stack.hh"
/* function prototypes */
bool isOperator( const char c );
std::string strip( const std::string &s );
std::string parse( const std::string &A, const std::string &B, const char op );
double eval( const std::string &s);
int prec( const char c );
std::string postfix( const std::string &s );
/* main function */
int main() {
std::string s;
while ( true ) {
try {
std::cout << "Enter text evaluate ( press $ to end ): \n";
std::cout << "> ";
std::getline( std::cin, s );
if ( s == "$" )
break;
std::cout << eval( s ) << "\n";
} catch ( std::runtime_error &e ) {
std::cout << "Invalid expression" << std::endl;
}
}
}
bool isOperator( const char c ) {
const char op[] = "+*/-()^";
static constexpr size_t size = sizeof( op ) / sizeof(op[0]);
for( unsigned i = 0; i != size; ++i ) {
if ( c == op[ i ] )
return true;
}
return false;
}
std::string strip( const std::string &s ) {
/* remove all invalid characters */
std::string n;
for( auto &c : s ) {
if( isdigit( c ) || isOperator( c ) ) {
n += c;
}
}
return n;
}
int prec( const std::string &c ) {
if ( c == "^" )
return 3;
if ( c == "*" || c == "/" )
return 2;
if ( c == "+" || c == "-" )
return 1;
return -1;
}
std::string postfix( const std::string &s ) {
/* convert to postfix */
emptyStack();
push("N");
int l = s.size();
std::string ns, temp;
for( int i = 0; i != l; ++i ) {
temp = "";
temp.push_back( s[ i ]);
if( isdigit( s[i] ) ) {
ns += temp;
}
else if( temp == "(" ) {
push("(");
}
else if( temp == ")" ) {
// if closing parentheses is found, pop the stack till equivalent opening parentheses;
while( peek() != "N" && peek() != "(" ) {
std::string c = peek();
pop();
ns += c;
}
if( peek() == "(" ) {
pop();
}
}
else if( peek() == "(" ) {
push( temp );
}
else {
while( peek() != "N" && prec( temp ) <= prec( peek() ) ) {
/* use precedence rule to compare operators */
std::string c = peek();
pop();
ns += c;
}
push( temp );
}
}
while( peek() != "N" ) {
// pop remaining element from the stack
std::string c = peek();
pop();
ns += c;
}
return ns;
}
std::string parse( const std::string &A, const std::string &B, const char op ) {
std::string result;
switch (op) {
case '^':
result = std::to_string( std::pow( std::stod( A ), std::stod( B ) ) ) ;
std::cout << result;
break;
case '*':
result = std::to_string( std::stod( A ) * std::stod( B ) );
break;
case '/':
result = std::to_string( std::stod( A ) / std::stod( B ) );
break;
case '+':
result = std::to_string( std::stod( A ) + std::stod( B ) );
break;
case '-':
result = std::to_string( std::stod( A ) - std::stod( B ) );
break;
default:
throw std::invalid_argument("Invalid operator.");
break;
}
return result;
}
double eval( const std::string &s) {
std::string newStr = s;
newStr = strip( newStr );
newStr = postfix( newStr );
emptyStack(); // deletes all contents in the stack and prepares stack for reuse
std::string temp; // temp string to store each character for evaluation
std::string result;
size_t l = newStr.size();
for( size_t i = 0; i != l; ++i ) {
temp = ""; // reset the string temp for reuse in the next evaluation
if( isdigit( newStr[i] ) ) {
temp.push_back( newStr[ i ] );
push( temp );
}
if( isOperator( newStr[ i ] ) ) {
// If an operator is found, pop out 2 operands from the stack
// and evaluate them
std::string A = peek();
pop();
std::string B = peek();
pop();
result = parse( B, A, newStr[ i ] );
push(result);
}
}
result = peek(); // The result is the top of the stack
pop();
return std::stod( result );
}
stack.hh
#ifndef STACK__
#define STACK__
struct Stack{
std::string data;
Stack *link;
};
void push( std::string x );
void pop();
std::string peek();
void insertAtBottom( std::string x );
void reverse();
int size();
bool isEmpty();
void emptyStack();
void display();
#endif;
stack.cc
#include <iostream>
#include <string>
#include "stack.hh"
Stack *top = nullptr;
void push( std::string x ) {
Stack *newNode = new Stack;
newNode->data = x;
newNode->link = top;
top = newNode;
}
void pop() {
if( top == nullptr ) {
throw std::runtime_error("List is empty");
}
Stack *temp = top;
top = top->link;
delete temp;
}
std::string peek() {
if( top == nullptr ) {
throw std::runtime_error("List is empty");
}
Stack *temp = top;
std::string x = temp->data;
return x;
}
void insertAtBottom( std::string x ) {
if ( top == nullptr )
push( x );
else {
std::string a = peek( );
pop( );
insertAtBottom( x );
push( a );
}
}
void reverse() {
if( top == nullptr )
return;
else {
std::string a = peek();
pop( );
reverse( );
insertAtBottom( a );
}
}
int size() {
Stack *temp = top;
int count = 0;
while( temp != nullptr ) {
temp = temp->link;
++count;
}
return count;
}
bool isEmpty() { return ( top == nullptr ); }
void emptyStack() {
while( isEmpty() == false ) {
pop();
}
}
void display() {
Stack *temp = top;
while( temp != nullptr ) {
std::cout << temp->data << " ";
temp = temp->link;
}
}
```
2+3*4
Should be14
. \$\endgroup\$