Computing Arithmetic Expressions given as Strings: C++ Solution

The most basic task any programming language should be able to handle is to compute arithmetic expressions including constants, numbers, variables as well as function calls and other value holding “objects”. I’ve written a simple C++ solution that can solve very simple arithmetic expressions. I think it’s a good starting point for anybody trying to deal with this problem when starting from scratch.

/*
    Task: Arithmetic Expression
   
          Calculate value of an nonnegative integer arithmetic expression given
          as a string and supporting + * / % (- excluded for simplicity)
          Ignore all charachters which ar not a digit or an operation (+ * / %)
          also detect division by zero and invalid or empty expression!
             
    Solution: Kristijan Burnik, Udruga informatičara Božo Težak
              GMail: kristijanburnik
             
    Complexity: Three passes
        Step 2: o(N) - Linear : where N denotes length of string
        Step 3: o(N~) - Linear : where N~ denotes number of tokens
        Step 4: o(N~) - Linear : where N~ denotes number of tokens
                        (rotating of tokens back/forth is o(1) )
   
    Strucutres: String, Vector & Double ended Queue
   
    Date: 31.01.2012.
   
    ----
   
    Test input  : 13 + 22 * 5 / 11 + 92 + 3%2
    Test output : 116
                 (exit code 0)
 
    Test input  :
    Test output : Empty expression!
                 (exit code -1)
   
    Test input  :  7 + + 5
    Test output : Invalid expression!
                 (exit code -2)
       
    Test input  : 7 / 0 + 5
    Test output : Division by zero!
                 (exit code -3)
   
*/
#include <iostream>
#include <cstdlib>
#include <vector>
#include <queue>
 
using namespace std;
 
typedef long long int llint;
typedef pair <int,string> token;
#define Type first
#define Value second
#define mp make_pair
 
const int NUMBER = 0, OPERATION = 1, OTHER = 2;
 
int get_type(char c) {
    if  (c >= '0' && c <= '9') return NUMBER;
    if (c == '*' || c == '+' || c == '/' || c == '%' ) return OPERATION;
    if (c == '~') return OPERATION; // sentinel
    return OTHER;    
}
 
// when operator a has greater priority than b
bool greater_priority(token a, token b) {
    return (( a.Value=="*" || a.Value=="/" || a.Value=="%" ) && b.Value == "+");
}
 
// integer to string conversion
string to_string(llint x) {
    string s;
    while (x > 0) {
        s = (char)((x%10)+'0') + s;
        x/=10;
    }
    return s;
}
 
// string to integer conversion
llint to_int(string s) {
    llint x = 0;
    for (int i = 0; i < s.size() ; i++ ) {
         x = x*10 + ((llint)(s[i]-'0'));
    }
    return x;
}
 
int main(void) {
 
////////////////////////////////////////////////////////////////////////////////
// STEP 1: input arithmetic expression: NON-NEG integers and + * / % operations
////////////////////////////////////////////////////////////////////////////////
 
    string s;
    getline(cin,s);
 
////////////////////////////////////////////////////////////////////////////////
// STEP 2: tokenize the expression
////////////////////////////////////////////////////////////////////////////////
 
    // add sentinel operation ~
    s += "~";    
   
    bool found_numbers = false;
    vector < token > tokens;
    string buffer;
    for (int i = 0; i  < s.size(); i++) {
        char c = s[i];
        int type = get_type(c);
        switch(type) {
            case NUMBER:
                buffer += c;
                found_numbers = true;
            break;
            case OPERATION:
                if (!found_numbers) {
                    cout << "Empty expression!" << endl;
                    exit(-1);    
                }
                if (buffer.size() > 0) {
                    tokens.push_back(mp(NUMBER,buffer));
                    buffer = "";
                }
                tokens.push_back(mp(OPERATION,s.substr(i,1)));
                   
            break;  
        }
        int ts = tokens.size();
        if (ts > 1 && tokens[ts-1].Type == tokens[ts-2].Type) {
            cout << "Invalid expression!" << endl;
            exit(-2);    
        }
    }
     
     // remove the sentinel operation ~
     tokens.pop_back();
 
////////////////////////////////////////////////////////////////////////////////
// STEP 3: Derive infix to sufix notation with priority handling!
////////////////////////////////////////////////////////////////////////////////
 
    deque <token> calc,ops;
    string last_op;
    for (int i = 0; i < tokens.size(); i++) {
            calc.push_back(tokens[i]);
            int cs = calc.size();
           
            switch (tokens[i].Type) {
                case NUMBER:
                    if (last_op != "") {
                        swap(calc[cs-1],calc[cs-2]);
                        last_op = "";
                    }
                break;
                case OPERATION:
                    last_op = tokens[i].Value;
                    ops.push_back(tokens[i]);
                break;    
            }
           
            int os = ops.size();
           
            // handle priority if needed
            if ( os > 1 && tokens[i].Type == NUMBER ) {
                if (greater_priority( ops[os-1], ops[os-2] ) ) {
                    swap( calc[cs-3] , calc[cs-2]);                        
                    swap( calc[cs-2] , calc[cs-1]);
                    swap( ops[os-1], ops[os-2] );
                }    
            }
    }
 
 
////////////////////////////////////////////////////////////////////////////////
// STEP 4: Calculate the expression from the sufix denoted tokens
////////////////////////////////////////////////////////////////////////////////
 
    token a, b, op, result = mp(NUMBER,"0");
    int atback = 0;
    while (calc.size() > 1) {
         
        // obtain first three tokens ( hope for A B OP respectivley )
        a = calc[0]; // first operand
        b = calc[1]; // second operand
        op = calc[2]; // operation
       
        // Check if A, B and OP correspond to their expected token type:
        // Priority handling: keep waiting operands at end of dequeue if needed
        if (op.Type != OPERATION) {
            // move the waiting operand to end of dequeue, and skip this round
            calc.push_back(a);
            calc.pop_front();
           
            // keep track of the waiting operands: will restore them after calc
            atback++;
           
        } else {
           // ready for calculating result, remove the front A, B and OP
            calc.pop_front(); calc.pop_front(); calc.pop_front();
 
            // the essence of the calculation is done here
            if (op.Value == "*") {
                result.Value = to_string( to_int(a.Value) * to_int(b.Value) );
            } else if (op.Value == "+") {
                result.Value = to_string( to_int(a.Value) + to_int(b.Value) );
            } else {
                // check for division by zero
                if (to_int(b.Value) == 0) {
                    cout << "Division by zero!" << endl;
                    exit(-3);
                }
                if (op.Value == "/") {
                    result.Value = to_string( to_int(a.Value) / to_int(b.Value) );
                } else if (op.Value == "%") {
                    result.Value = to_string( to_int(a.Value) % to_int(b.Value) );                
                }
        }
           
            // insert the result to its place for rest of the calculation
            calc.push_front(result);
           
            // restore the waiting operands from back to front
            while (atback-- > 0) {
                    calc.push_front(calc.back());
                    calc.pop_back();
            }
            atback = 0;
       
        }
       
    }
   
////////////////////////////////////////////////////////////////////////////////
// STEP 5: output result  
////////////////////////////////////////////////////////////////////////////////
 
    cout << calc.front().Value << endl;
 
    return 0;
}

The source code is also available on my pastebin:

Coding Examples, Open Source | Posted on July 2, 2013 by .

About Kristijan Burnik

Kristijan Burnik is a Programmer and Web Developer specializing in Server-side and Client-side Technologies and Application Development on Linux Servers and Windows Desktop . Also has experience in Networking, Desktop application development as well as Android mobile application development . Experienced in Programming Languages like Java, C, C++, C#, PHP, Javascript, MySQL and somewhat in other languages like Bash, Perl & Python. Sometimes he works as a Graphical Designer for digital production as well as for printing and advertising. He dedicates his spare time writing Tech Articles on his blog in order to share his work with others, as well as to document his projects for his own use. He's also an Educator & Mentor in field of Algorithms and Programming to young programmers in Zagreb, Croatia.

Leave a Reply