simple calculator

This is a discussion on simple calculator within the C++ Programming forums, part of the General Programming Boards category; I'm writing a simple calculator program. At first I wrote program that converts infix to postfix notation and I thought ...

  1. #1
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712

    simple calculator

    I'm writing a simple calculator program. At first I wrote program that converts infix to postfix notation and I thought it would be simple thing to evaluate exression. This calculator is working with integers numbers only for the start. However I have a bug, for example -2*4-5 will not work because of the way of string processing I've chosen. That charatcer '-' is converted to some number. I would like you to aks for help, to give me advice how to change string processing, or maybe to start writing program from the scratch. I omitted error checking for simplicity.
    Can you suggest me the way to fix this without large program modifications? It seems that this idea is not very useful. how would you approach to this problem?

    Thank you very much

    Code:
    #include <iostream>
    #include <string>
    #include <algorithm>
    #include <cctype>
    #include <stack>
    #include <cstdlib>
    #include <cmath>
    
    using namespace std;
    
    inline bool is_whitespace (const char&);
    inline bool is_operator (const char&);
    inline bool is_operand (const char&);
    inline bool higher_priority (const char&, const char&);
    inline bool same_priority (const char&, const char&);
    int get_priority (const char&);
    string remove_whtsp (string&);//remove whitespace characters 
    string convert_to_postfix (string&);
    long postfix_eval (string&);
    
    
    int main()
    {
    	string a;
    	getline (cin, a);
    	string b = remove_whtsp (a);
    	string c = convert_to_postfix (b);
    	cout << (c)<<endl;
    	cout << postfix_eval(c);
    
    	return 0;
    }
    
    bool is_whitespace(const char& ch)
    {
    	return (isspace(ch) != 0);
    }
    
    bool is_operator (const char& ch)
    {
    	return (ch == '+' || ch == '*' || ch == '/' || ch == '-' || ch == '^');
    }
    
    bool is_operand (const char& ch)
    {
    	return (isdigit(ch) != 0 || isalpha(ch) != 0);
    }
    
    bool higher_priority (const char& ch, const char& top)
    {
    	return get_priority(ch) > get_priority(top);
    }
    
    inline bool same_priority (const char& ch, const char& top)
    {
    	return get_priority (ch) == get_priority (top);
    }
    
    int get_priority (const char& ch)
    {
    	if (ch == '^') return 3;
    	else if (ch == '*' || ch == '/') return 2;
    	else if (ch == '+' || ch == '-') return 1;
    	else return 0;
    }
    
    string remove_whtsp (string& a)
    {
    	string b;
    	remove_copy_if(a.begin(), a.end(), back_inserter(b), is_whitespace);
    	return b;
    }
    
    string convert_to_postfix (string& str_infix)
    {
    	stack <char> st;
    	string str_postfix;
    
    	string :: const_iterator it;
    	it = str_infix.begin();
    	//step1. Examine the next element in the input.
    	while (it != str_infix.end())
    	{
    		if (is_operand(*it)) 
    		{
    			str_postfix.push_back(*it);//step 2. If it is an operand, output it.
    		}
    		else if (*it == '(') 
    		{
    			st.push(*it);//step 3. If it is opening parenthesis, push it on stack.
    		}
    		else if (is_operator(*it))//step4. If it is an operator, then
    		{
    			if (st.empty()) 
    			{
    				st.push(*it);
    			}
    			else if (same_priority(st.top(), *it))
    			{
    				str_postfix.push_back(st.top());
    				st.pop();
    				st.push(*it);
    			}
    			else if (higher_priority(*it, st.top()))
    			{
    				st.push(*it);
    			}
    			else
    			{
    				while (!higher_priority(*it, st.top()))
    				{
    					str_postfix.push_back(st.top());
    					st.pop();
    				}
    				st.push(*it);
    			}
    		}//end step 4.
    		if (*it == ')')//step 5.If it is a closing parenthesis, 
    //pop operators from the stack and output them until an opening parenthesis is encountered 
    		{
    			while (st.top() != '(')
    			{
    					str_postfix.push_back(st.top());
    					st.pop();
    			}
    			st.pop();
    		}
    		++it;
    	}
    	while (!st.empty())//step7. If there is no more input, unstack the remaining operators to output.
    	{
    		str_postfix.push_back (st.top());
    		st.pop();
    	}
    
    	return str_postfix;
    }
    
    long postfix_eval(string& str)
    {
    	string tmp;
    	string :: const_iterator it;
    	stack <long> st;
    	long temp1, temp2;
    
    	for (it = str.begin(); it != str.end(); ++it)
    	{
    		if (is_operand(*it))
    		{
    			tmp = *it;
    			st.push(atol(tmp.c_str()));
    			tmp = "";
    		}
    		else if (is_operator(*it))
    		{
    			temp1 = st.top();
    			st.pop();
    			temp2 = st.top();
    			st.pop();
    			if (*it == '+')
    			{
    				st.push(temp1 + temp2);
    			}
    			else if(*it == '-')
    			{
    				st.push(temp2 - temp1);
    			}
    			else if(*it == '*')
    			{
    				st.push(temp1 * temp2);
    			}
    			else if(*it == '/')
    			{
    				st.push(temp2 / temp1);
    			}
    			else if (*it == '^')
    			{
    				st.push(static_cast<long>(pow(temp2, temp1)));//I had to do casting
    			}
    		}
    	}
    	temp1 = st.top();
    	st.pop();
    	return temp1;
    }
    - Micko
    Gotta love the "please fix this for me, but I'm not going to tell you which functions we're allowed to use" posts.
    It's like teaching people to walk by first breaking their legs - muppet teachers! - Salem

  2. #2
    Registered User
    Join Date
    Nov 2002
    Posts
    491
    This is probably not what you want to hear but the easiest way to do this would probably be using lex & yacc. You can define a grammar which tokenises the integers and operators and gives you a tree structure. After that you just iterate through the tree and evaluate the expressions.
    I have not done this myself in lex & yacc but I have written the basic grammar in yecc:
    Code:
    Nonterminals expr statement function params.                                                                                                                                                                     
                                                                                                                                                                                                                     
    Terminals 'integer' 'var' '+' '-' '*' '/' '(' ')' '=' ',' 'and' 'or' '=='.                                                                                                                                       
                                                                                                                                                                                                                     
    Rootsymbol statement.                                                                                                                                                                                            
                                                                                                                                                                                                                     
    Left 100 '+'.                                                                                                                                                                                                    
    Left 100 '-'.                                                                                                                                                                                                    
    Left 100 'or'.                                                                                                                                                                                                   
    Left 200 '*'.                                                                                                                                                                                                    
    Left 200 '/'.                                                                                                                                                                                                    
    Left 200 'and'.                                                                                                                                                                                                  
    Unary 600 '-'.                                                                                                                                                                                                   
    Unary 600 '+'.                                                                                                                                                                                                   
                                                                                                                                                                                                                     
    statement -> statement ',' statement : {sequence, '$1', '$3'}.                                                                                                                                                   
    statement -> expr : '$1'.                                                                                                                                                                                        
    statement -> function : '$1'.                                                                                                                                                                                    
                                                                                                                                                                                                                     
    expr -> expr '+' expr : {add, '$1', '$3'}.                                                                                                                                                                       
    expr -> expr '-' expr : {subtract, '$1', '$3'}.                                                                                                                                                                  
    expr -> expr '*' expr : {multiply, '$1', '$3'}.                                                                                                                                                                  
    expr -> expr '/' expr : {divide, '$1', '$3'}.                                                                                                                                                                    
    expr -> expr 'and' expr : {land, '$1', '$3'}.                                                                                                                                                                    
    expr -> expr 'or' expr : {lor, '$1', '$3'}.                                                                                                                                                                      
    expr -> expr '==' expr : {eq, '$1', '$3'}.                                                                                                                                                                       
    expr -> '(' expr ')' : '$2'.                                                                                                                                                                                     
    expr -> '-' expr : {negative, '$2'}.                                                                                                                                                                             
    expr -> '+' expr : {positive, '$2'}.                                                                                                                                                                             
    expr -> 'integer' : '$1'.                                                                                                                                                                                        
    expr -> 'var' '(' params ')' : {funccall, '$1', '$3'}.                                                                                                                                                           
    expr -> 'var' '(' ')' : {funccall, '$1', nil}                                                                                                                                                                    
    expr -> 'var' : {funccall, '$1', nil}.                                                                                                                                                                           
                                                                                                                                                                                                                     
    function -> 'var' '(' params ')' '=' expr : {funcdef, '$1', '$3', '$6'}.                                                                                                                                         
    function -> 'var' '(' ')' '=' expr : {funcdef, '$1', nil, '$5'}.                                                                                                                                                 
                                                                                                                                                                                                                     
    params -> 'var' ',' params : {param, '$1', '$3'}.                                                                                                                                                                
    params -> 'var' : {param, '$1', nil}.
    That is a bit more complex and allows you to do assignment. However this is just a starting point and probably more than what you want.
    To actually answer the question you asked:
    A good idea would probably be to, isntead of making a new postfix string, create a tree which represents the expression and then recurse through the tree to evaluate. In order to evaluate the string you should write a finite state machine. This means instead of looking for an operator such as '-' or '+', and assuming it's a binary operator you figure out what it should be based on the current state and the input token. So for instance to evaluate "-2" you would first probably wan tot break it up into tokens, in this case you have '-' being an operator, then '2' being a number. Then you evaluate this data with a fsm. you have an initial state, you see the '-' operator, and decide wether to reduce or shift, move onto a new state, see the '2' and decide to reduce or shift.
    I think that, if anything, I have just made your much more confused about what is going on but perhaps I have given you some good google search terms. If you ask some more questions I'll try to take the time to give you more useful and coherent answers.
    Sorry

  3. #3
    Banned
    Join Date
    Jun 2005
    Posts
    594
    you are already using string maybe stringstream could
    help you in this situation.

  4. #4
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    Yeah probably use a binary tree or linked list of some sort. Since the fundamental properties of a binary tree make it ideal for dealing with basic arithmetic or algebra .

    For example, since multiplication has priority over the other operators it would occupy the root node in the binary tree. The other operators, such as '+' and '-' would be positioned below the '*' and '/' . Then it would be a case of recursively evaluating
    each expression as you traverse through the tree. (what orbitz said me thinks).

    The link below should give you some practical ideas where and how to approach this.

    algebra solver

  5. #5
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    Thanks for replies, I'll be very busy next week, but after that I'll be back (hopefuly) with solution or with further questions.

    - Micko
    Gotta love the "please fix this for me, but I'm not going to tell you which functions we're allowed to use" posts.
    It's like teaching people to walk by first breaking their legs - muppet teachers! - Salem

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Simple Socialising Chat Bots
    By bengreenwood in forum C++ Programming
    Replies: 10
    Last Post: 11-28-2007, 07:42 AM
  2. simple calculator
    By HunterCS in forum C++ Programming
    Replies: 10
    Last Post: 07-18-2007, 06:51 AM
  3. A Simple Calculator Program Not Working
    By oobootsy1 in forum C++ Programming
    Replies: 9
    Last Post: 01-09-2004, 08:34 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. Simple simple graphics
    By triplem in forum C Programming
    Replies: 2
    Last Post: 05-19-2003, 02:52 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21