By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
434,636 Members | 1,941 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 434,636 IT Pros & Developers. It's quick & easy.

conversion from infix to postfix

P: 24
Hi... I need a program to convert an infix arithmetic expression to postfix with the use of stacks... Can anyone tell me how do i go about implementing this? thanks
Sep 17 '06 #1
Share this Question
Share on Google+
11 Replies


100+
P: 293
D_C
There is a standard algorithm to do this. The last paragraph of this website has the steps.

Print the numbers out in normal order, push parenthesis and operators onto the stack. When parenthesis line up, ignore them, don't print anything. If they don't line up, that's an error. Then, depending upon priority of the operator (PEMDAS) push or pop the operator off the stack. If you pop it, display it in the output.

The website explains it better, why don't you go have a look.
Sep 17 '06 #2

P: 24
Nhd
Hi can anyone help me to check this... Im lost in my own program... I noe some part of it is wrong... can anyone tell me... thanks

#include <iostream>
#include <stack>
#include <vector>
#include <sstream>
using namespace std;

int main()
{
string line, str;
int number;

cout<<"Sample Input 1"<<" "<<endl;
cin>>line;

getline(cin, line);
istringstream iss(line); //create string stream

while(!iss.eof())
{
iss >> str; //reads from iss into str until next space is met
}

//Postfix evaluation
int eval_postfix(const vector<char>&v, stack<int>&st)
{
for (vector<char>::const_iterator str = v.begin(begin(); str !=v.end(); ++str)
{
if ('0'<= str && str<='9')
st.push(str-'0')
else
{
int arg2 = st.top();
st.pop();
int arg1 = st.top();
st.pop();
int result;

if (str == "+" || str == "-") //when you compare for char, it's '+' and '-'
{
case '+': result = arg1 + arg2;
return 1;
break;
case '-': result = arg1 - arg2;
resturn 2;
break;
}
else if (str == "*" || str == "/")
{
case '*': result = arg1 * arg2;
break;
return 3;
case '/': result = arg1 / arg2;
break;
return 4;
} //end if else

st.push(result);
} //end else
}//end for

int i = st.top();
st.pop();
return i;
}//end eval_postfix


system("pause");
return 0;
}
Sep 20 '06 #3

P: 24
Nhd
Hi i modify my codes but i'm unable to execute it.... can anyone help me to spot the mistake.. thanks

Expand|Select|Wrap|Line Numbers
  1. #include <iostream>
  2. #include <stack>
  3. #include <vector>
  4. #include <sstream>
  5. using namespace std;
  6.  
  7. int main()
  8. {
  9.       string line, str;  
  10.       int number;
  11.  
  12.       cout<<"Sample Input:"<<" "<<endl;
  13.       cin>>line;
  14.  
  15.       getline(cin, line);
  16.       istringstream iss(line); //create string stream
  17.  
  18.       while(!iss.eof()) 
  19.       {
  20.            iss >> str; //reads from iss into str until next space is met
  21.       }
  22.  
  23.       //Code of Postfix Evaluation
  24.       int eval_postfix(const vector<char>&v, stack<int>&st)
  25.       {
  26.           for (vector<char>::const_iterator ptr = v.begin(begin(); ptr !=v.end(); ++ptr)
  27.           {
  28.               if ('0'<= *ptr && *ptr<='9')
  29.               st.push(*ptr-'0')
  30.               else
  31.               {
  32.                   int arg2 = st.top();
  33.                   st.pop();
  34.                   int arg1 = st.top();
  35.                   st.pop();
  36.                   int result;
  37.  
  38.               switch (*ptr)
  39.               {
  40.                      case '+': result = arg1 + arg2;
  41.                      break;
  42.                      case '-': result = arg1 - arg2;
  43.                      break;
  44.                      case '*': result = arg1 * arg2;
  45.                      break;
  46.                      case '/': result = arg1 / arg2;
  47.                      break; 
  48.               } //end switch
  49.               st.push(result);
  50.               } //end else
  51.           }//end for
  52.  
  53.           int i = st.top();
  54.           st.pop();
  55.           return i;
  56.       }//end eval_postfix 
  57.  
  58.        cout<<i<<"Sample Output:"<<" "<<endl;
  59.  
  60.        system("pause");
  61.        return 0;
  62. }
  63.  
Sep 20 '06 #4

Banfa
Expert Mod 5K+
P: 8,916
You have tried to define the function

int eval_postfix(const vector<char>&v, stack<int>&st)

inside the function

int main()

This is not allowed in C/C++ move the definition of the function eval_postfix outside the function main.
Sep 20 '06 #5

P: 24
Nhd
Hi... I put the "int eval_postfix(const vector<char>&v, stack<int>&st)" out of the main, i still get error.. the error i get is something to do with this "int main()".. but i cant remove the "int main()"..... I'm sory to bother u but im really weak in my programming...

#include <iostream>
#include <stack>
#include <vector>
#include <sstream>
using namespace std;
int eval_postfix(const vector<char>&v, stack<int>&st)
int main()
{
string line, str;
int number;
char *cstr;

cout<<"Sample Input:"<<" "<<endl;
cin>>line;

getline(cin, line);
istringstream iss(line); //create string stream

while(!iss.eof())
{
iss >> str; //reads from iss into str until next space is met
}

//Code of Postfix Evaluation
for (vector<char>::const_iterator ptr = v.begin(begin(); ptr !=v.end(); ++ptr)
{
if ('0'<= *ptr && *ptr<='9')
st.push(*ptr-'0')
else
{
int arg2 = st.top();
st.pop();
int arg1 = st.top();
st.pop();
int result;

switch (*ptr)
{
case '+': result = arg1 + arg2;
break;
case '-': result = arg1 - arg2;
break;
case '*': result = arg1 * arg2;
break;
case '/': result = arg1 / arg2;
break;
} //end switch
st.push(result);
} //end else
}//end for

int i = st.top();
st.pop();
return i;
}//end eval_postfix

//convert string to integer
number = atoi(str.c_str()); //now number is 1234

//convert integer into string
sprintf(cstr, "%d", number); //print number into cstring
string str(cstr); //makes cstring a string

//checking if all characters of the string are digits
cstr = str.c_str();
if ( isdigit(*cstr) ) //checks the first character of cstr is digit or not
return true;

cout<<"Sample Output:"<<cin<<" "<<endl;

system("pause");
return 0;
}
Sep 20 '06 #6

Banfa
Expert Mod 5K+
P: 8,916
You have to move the entire function, not just the header line

This
Expand|Select|Wrap|Line Numbers
  1. int main()
  2. {
  3.   // main code
  4.  
  5.   int fn()
  6.   {
  7.     // function code
  8.   }
  9.  
  10.   // more main code
  11. }
  12.  
becomes

Expand|Select|Wrap|Line Numbers
  1. int fn();
  2.  
  3. int main()
  4. {
  5.   // main code
  6.  
  7.   // more main code
  8. }
  9.  
  10. int fn()
  11. {
  12.   // function code
  13. }
  14.  
  15.  
  16.  
Sep 20 '06 #7

P: 24
Nhd
for this function, for the 2nd sentence , may i noe how do i declare "begin"? i hav error regarding this.... should i declare it in main function or in its own function itself...

int eval_postfix(const vector<char>&v, stack<int>&st)
{
for (vector<char>::const_iterator ptr = v.begin(begin(); ptr !=v.end(); ++ptr)
{
if ('0'<= *ptr && *ptr<='9')
st.push(*ptr-'0');
else
{
int arg2 = st.top();
st.pop();
int arg1 = st.top();
st.pop();
int result;

switch (*ptr)
{
case '+': result = arg1 + arg2;
break;
case '-': result = arg1 - arg2;
break;
case '*': result = arg1 * arg2;
break;
case '/': result = arg1 / arg2;
break;
} //end switch
st.push(result);
} //end else
}//end for

int i = st.top();
st.pop();
return i;
}//end eval_postfix
Sep 20 '06 #8

Banfa
Expert Mod 5K+
P: 8,916
Not really sure what you are saying but

for (vector<char>::const_iterator ptr = v.begin(begin(); ptr !=v.end(); ++ptr)

should be

for (vector<char>::const_iterator ptr = v.begin(); ptr !=v.end(); ++ptr)
Sep 20 '06 #9

P: 24
Nhd
Thanks Banfa for ur help.... but do u mind helping me to check my program please.... I've been struggling from juz now and i still cant do it....

Expand|Select|Wrap|Line Numbers
  1. #include <iostream>
  2. #include <stack>
  3. #include <vector>
  4. #include <sstream>
  5. using namespace std;
  6.  
  7. int eval_postfix(const vector<char>&v, stack<int>&st);
  8. int main()
  9. {
  10.       string line, str;
  11.       int number;
  12.       char *cstr;
  13.  
  14.       cout<<"Sample Input:"<<" "<<endl;
  15.       cin>>line;
  16.  
  17.       getline(cin, line);
  18.       istringstream iss(line); //create string stream
  19.  
  20.       while(!iss.eof()) 
  21.       {
  22.        iss >> str; //reads from iss into str until next space is met
  23.       }
  24.  
  25.       //convert string to integer
  26.       number = atoi(str.c_str()); //now number is 1234
  27.  
  28.       cout<<"Sample Output:"<<str<<" "<<endl;
  29.  
  30.       system("pause");
  31.       return 0;
  32. }
  33.  
  34.      //Code of Postfix Evaluation
  35.       int eval_postfix(const vector<char>&v, stack<int>&st)
  36.       {
  37.           for (vector<char>::const_iterator ptr = v.begin(); ptr !=v.end(); ++ptr)
  38.           {
  39.               if ('0'<= *ptr && *ptr<='9')
  40.               st.push(*ptr-'0');
  41.               else
  42.               {
  43.                   int arg2 = st.top();
  44.                   st.pop();
  45.                   int arg1 = st.top();
  46.                   st.pop();
  47.                   int result;
  48.  
  49.               switch (*ptr)
  50.               {
  51.                      case '+': result = arg1 + arg2;
  52.                      break;
  53.                      case '-': result = arg1 - arg2;
  54.                      break;
  55.                      case '*': result = arg1 * arg2;
  56.                      break;
  57.                      case '/': result = arg1 / arg2;
  58.                      break; 
  59.               } //end switch
  60.               st.push(result);
  61.               } //end else
  62.           }//end for
  63.  
  64.           int i = st.top();
  65.           st.pop();
  66.           return i;
  67.       }//end eval_postfix 
  68.  
  69.       //Conversion from Infix to Postfix expression
  70.       vector<char> postFix;
  71.       for (vector<char>::const_iterator ptr = v.begin(); ptr !=v.end(); ++ptr)
  72.       {
  73.         switch(ch)
  74.         {
  75.                   case operand: 
  76.                        postfixExp = postfixExp + ch;
  77.                        break;
  78.                   case '(': 
  79.                        Stack.push (ch);
  80.                        Break;
  81.                   case ')':
  82.                        while (stack.top()!='(')
  83.                        {
  84.                              postfixExp = postfixExp + stack.top();
  85.                              Stack.pop();
  86.                        } //end while
  87.  
  88.                        Stack.pop();
  89.                        break;
  90.  
  91.                   //infix to postfix - use stack for storing operators
  92.                   case operator:
  93.  
  94.                        while (!Stack.isEmpty() && Stack.top != '(' && precedence(ch) >= precedence(stack.top()))
  95.                        {
  96.                              postfixExp = postfixExp + Stack.top();
  97.                              Stack.pop();
  98.                         } end while
  99.              }//end switch
  100.  
  101.     } //end for
  102.  
  103.     while (!Stack.isEmpty())
  104.     {
  105.           postfixExp = postfixExp + Stack.top();
  106.           Stack.pop()
  107.     }// end while
  108.  
Sep 20 '06 #10

Banfa
Expert Mod 5K+
P: 8,916
None of this code

Expand|Select|Wrap|Line Numbers
  1.       //Conversion from Infix to Postfix expression
  2.       vector<char> postFix;
  3.       for (vector<char>::const_iterator ptr = v.begin(); ptr !=v.end(); ++ptr)
  4.       {
  5.         switch(ch)
  6.         {
  7.                   case operand: 
  8.                        postfixExp = postfixExp + ch;
  9.                        break;
  10.                   case '(': 
  11.                        Stack.push (ch);
  12.                        Break;
  13.                   case ')':
  14.                        while (stack.top()!='(')
  15.                        {
  16.                              postfixExp = postfixExp + stack.top();
  17.                              Stack.pop();
  18.                        } //end while
  19.  
  20.                        Stack.pop();
  21.                        break;
  22.  
  23.                   //infix to postfix - use stack for storing operators
  24.                   case operator:
  25.  
  26.                        while (!Stack.isEmpty() && Stack.top != '(' && precedence(ch) >= precedence(stack.top()))
  27.                        {
  28.                              postfixExp = postfixExp + Stack.top();
  29.                              Stack.pop();
  30.                         } end while
  31.              }//end switch
  32.  
  33.     } //end for
  34.  
  35.     while (!Stack.isEmpty())
  36.     {
  37.           postfixExp = postfixExp + Stack.top();
  38.           Stack.pop()
  39.     }// end while
  40.  
Is inside a function and is causing a syntax error

It doesn't appear to have any purpose so I guess you can just delete it as the program compiles fine without it.
Sep 20 '06 #11

P: 24
Nhd
hi Banfa.. my purpose in typing out those codes is to convert infix to postfix..

for example:
Sample input 1
1 + 2 * 3 - 4 / 2 + 5 * 6
Sample output 1
35

Sample input 2
( 10 + 20 ) * 30 - 4000 / 20 + 50 * 60
Sample output 2
3700

I'm trying to write a program for this... and my notes shows only these codes, the one that i type out...

what should i do now... :(
Sep 20 '06 #12

Post your reply

Sign in to post your reply or Sign up for a free account.