I am trying to convert from infix to postfix, and then evaluating the postfix expression to get the final answer. I am having a severe problem though, because for some reason the conversion is not working at all. For example, when I input the first infix expression: 24 + 33 * ( 7 - 5 ) + 8 / 3 it outputs 24 33 7 5 45404243 8 34743 which is obviously very wrong. I am not really sure where the problem is though. Below I have included all of the code needed. I also had to create my own stack class, so I will include it too if it would help. Any tips would be greatly appreciated!
#include "stacks.h"
#include <iostream>
#include <string>
using namespace std;
bool IsOperand(char C)
{
if(C >= '0' && C <= '9') return true;
return false;
}
bool IsOperator(char C)
{
if(C == '+' || C == '-' || C == '*' || C == '/')
return true;
return false;
}
int GetOperatorWeight(char op)
{
int weight = -1;
switch(op)
{
case '+':
case '-':
weight = 1;
case '*':
case '/':
weight = 2;
}
return weight;
}
int HasHigherPrecedence(char op1, char op2)
{
int op1Weight = GetOperatorWeight(op1);
int op2Weight = GetOperatorWeight(op2);
return op1Weight > op2Weight ? true: false;
}
int PerformOperation(char operation, int operand1, int operand2)
{
if(operation == '+') return operand1 +operand2;
else if(operation == '-') return operand1 - operand2;
else if(operation == '*') return operand1 * operand2;
else if(operation == '/') return operand1 / operand2;
else cout<<"Unexpected Error \n";
return -1;
}
bool IsNumericDigit(char C)
{
if(C >= '0' && C <= '9') return true;
return false;
}
int evalPost(string item)
{
stacks S;
for(int i = 0;i< item.length();i++) {
if(item[i] == ' ' || item[i] == ',') continue;
else if(IsOperator(item[i])) {
int operand2 = stoi(S.stackTop()); S.pop();
int operand1 = stoi(S.stackTop()); S.pop();
int result = PerformOperation(item[i], operand1, operand2);
S.push(to_string(result));
}
else if(IsNumericDigit(item[i]))
{
int operand = 0;
while(i<item.length() && IsNumericDigit(item[i]))
{
operand = (operand*10) + (item[i] - '0');
i++;
}
i--;
S.push(to_string(operand));
}
}
return stoi(S.stackTop());
}
string infToPost(string item)
{
stacks S;
string postfix = "";
for(int i = 0;i< item.length();i++) {
cout<<postfix<<endl;
if(item[i] == ' ')
postfix +=item[i];
else if(IsOperator(item[i]))
{
while(!S.empty() && S.stackTop() != "(" && HasHigherPrecedence(*(S.stackTop().c_str()),item[i]))
{
postfix+= S.stackTop();
S.pop();
}
S.push(to_string(item[i]));
//S.pop();
}
else if(IsOperand(item[i]))
{
postfix +=item[i];
}
else if (item[i] == '(')
{
S.push(to_string(item[i]));
}
else if(item[i] == ')')
{
while(!S.empty() && S.stackTop() != "(") {
postfix += S.stackTop();
S.pop();
}
S.pop();
}
}
while(!S.empty()) {
postfix += S.stackTop();
S.pop();
}
return postfix;
}
int main()
{
string selection="";
string infix;
string postfix;
string eval;
cout<<"***********************************************************"<<endl;
cout<<"1. Read an expression in infix notation."<<endl;
cout<<"2. Convert infix to postfix."<<endl;
cout<<"3. Evaluate the expression using postfix notation."<<endl;
cout<<"4. Exit"<<endl;
cout<<"***********************************************************"<<endl;
cout<<"Select: ";
getline(cin, selection);
// cin>>selection;
// cin.ignore();
while (selection>"4" || selection<"1")
{
cout<< "Please enter a different choice (1-4): ";
getline(cin, selection);
}
while(selection!="4")
{
if (selection=="1")
{
cout<<"Enter an infix expression: ";
getline(cin,infix);
cout<<"\n";
}
if(selection=="2")
{
cout<<"Infix expression: "<<infix<<endl;
postfix = infToPost(infix);
cout<<"Postfix expression: "<<postfix<<endl;
cout<<"\n";
}
if(selection=="3")
{
cout<<"Infix expression: "<<infix<<endl;
eval = evalPost(postfix);
cout<<"Evaluation of this expression: "<<endl;
cout<<"\n";
}
selection = "";
cout<<"***********************************************************"<<endl;
cout<<"1. Read an expression in infix notation."<<endl;
cout<<"2. Convert infix to postfix."<<endl;
cout<<"3. Evaluate the expression using postfix notation."<<endl;
cout<<"4. Exit"<<endl;
cout<<"***********************************************************"<<endl;
cout<<"Select: ";
getline(cin,selection);
//cin.ignore();
while (selection>"4" || selection<"1")
{
cout<< "Please enter a different choice (1-4): ";
getline(cin, selection);
}
}
cout<<"Thank you for using my program."<<endl;
return 0;
}
STACK CLASS HEADER
#ifndef __Programming_Assingment_3__stacks__
#define __Programming_Assingment_3__stacks__
#include <string>
#include <vector>
using namespace std;
//define the stacks class
class stacks
{
public:
//constructor
stacks();
//push function
void push(string item);
//pop function
void pop();
//function to get top of stack
string stackTop();
//check if stack is empty
bool empty();
private:
//create vector and integer
int top;
vector<string> sstack;
};
#endif /* defined(__Programming_Assingment_3__stacks__) */
STACK CLASS CPP FILE
#include "stacks.h"
#include <iostream>
#include <string>
using namespace std;
//Contstructor
stacks::stacks()
{
top = -1;
}
//push the item onto the stack
void stacks::push(string item)
{
sstack.push_back(item);
top++;
}
//check if the stack is empty
bool stacks::empty()
{
if (top==-1)
return true;
else
return false;
}
//delete the last item on the stack
void stacks::pop()
{
try{
if (sstack.size()==0) throw 0;
} catch(int err){
cout<<"stack is empty."<<endl;
cout<<"Cannot pop an item."<<endl;
return;
}
sstack.pop_back();
top--;
}
//get the top of the stack
string stacks::stackTop()
{
try{
if (sstack.size()==0) throw 0;
} catch (int err) {
cout<< "stack is empty."<<endl;
return 0;
}
return (sstack[top]);
}
std::stack, then once it's working see if it works with your own stack... if not at least you know where to debug. – Tony Delroy