Skip to content

Instantly share code, notes, and snippets.

@mycodeschool
Created November 29, 2013 07:02
Show Gist options
  • Save mycodeschool/7702441 to your computer and use it in GitHub Desktop.
Save mycodeschool/7702441 to your computer and use it in GitHub Desktop.
/*
Evaluation Of postfix Expression in C++
Input Postfix expression must be in a desired format.
Operands must be integers and there should be space in between two operands.
Only '+' , '-' , '*' and '/' operators are expected.
*/
#include<iostream>
#include<stack>
#include<string>
using namespace std;
// Function to evaluate Postfix expression and return output
int EvaluatePostfix(string expression);
// Function to perform an operation and return output.
int PerformOperation(char operation, int operand1, int operand2);
// Function to verify whether a character is operator symbol or not.
bool IsOperator(char C);
// Function to verify whether a character is numeric digit.
bool IsNumericDigit(char C);
int main()
{
string expression;
cout<<"Enter Postfix Expression \n";
getline(cin,expression);
int result = EvaluatePostfix(expression);
cout<<"Output = "<<result<<"\n";
}
// Function to evaluate Postfix expression and return output
int EvaluatePostfix(string expression)
{
// Declaring a Stack from Standard template library in C++.
stack<int> S;
for(int i = 0;i< expression.length();i++) {
// Scanning each character from left.
// If character is a delimitter, move on.
if(expression[i] == ' ' || expression[i] == ',') continue;
// If character is operator, pop two elements from stack, perform operation and push the result back.
else if(IsOperator(expression[i])) {
// Pop two operands.
int operand2 = S.top(); S.pop();
int operand1 = S.top(); S.pop();
// Perform operation
int result = PerformOperation(expression[i], operand1, operand2);
//Push back result of operation on stack.
S.push(result);
}
else if(IsNumericDigit(expression[i])){
// Extract the numeric operand from the string
// Keep incrementing i as long as you are getting a numeric digit.
int operand = 0;
while(i<expression.length() && IsNumericDigit(expression[i])) {
// For a number with more than one digits, as we are scanning from left to right.
// Everytime , we get a digit towards right, we can multiply current total in operand by 10
// and add the new digit.
operand = (operand*10) + (expression[i] - '0');
i++;
}
// Finally, you will come out of while loop with i set to a non-numeric character or end of string
// decrement i because it will be incremented in increment section of loop once again.
// We do not want to skip the non-numeric character by incrementing i twice.
i--;
// Push operand on stack.
S.push(operand);
}
}
// If expression is in correct format, Stack will finally have one element. This will be the output.
return S.top();
}
// Function to verify whether a character is numeric digit.
bool IsNumericDigit(char C)
{
if(C >= '0' && C <= '9') return true;
return false;
}
// Function to verify whether a character is operator symbol or not.
bool IsOperator(char C)
{
if(C == '+' || C == '-' || C == '*' || C == '/')
return true;
return false;
}
// Function to perform an operation and return output.
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;
}
@saku123hh
Copy link

Here is my implemention, I have fixed the while loop error:
#include
using namespace std;
#include
#include

bool IsOperator(char x) {
if (x == '+' || x == '-' || x == '*') {
return true;
}
return false;
}

bool IsOperand(char x) {
// cout<<"x"<<x<<endl;
if (x <= '9' && x >= '0') return true;
return false;

}

int PerformOperation(char c, int x, int y) {
if (c == '+') return(x + y);
else if (c == '-') return(x - y);
else if (c == '*') return(x * y);
else cout << "unexpected error" << endl;
return -1;
}

void Print(stack S) {
while (!S.empty()) {
cout << S.top() << endl;
S.pop();
}
cout << "" << endl;
}

int EvaluatePostfix(string expression) {
stack S;

for (int i = 0; i < expression.length(); i++) {
    // cout<<IsOperator(expression[i])<<endl;
   //  cout<<IsOperand(expression[i])<<endl;
    if (expression[i] == ' ' || expression[i] == ',') continue;
    else if (IsOperator(expression[i])) {
        int operand2 = S.top(); S.pop();
        if (S.empty()) { cout << "Error: check your postfix" << endl; return -1; }
        int operand1 = S.top(); S.pop();
        int result = PerformOperation(expression[i], operand1, operand2);
        S.push(result);
        cout << "进入operatorS is:" << endl;
        Print(S);
    }

    else if (IsOperand(expression[i])) {
        int operand = 0;
        while (IsOperand(expression[i]) && i < expression.length()) {
            operand = operand * 10 + (expression[i] - '0');
            i++;
            cout << i << endl;
        }
        i--;  //比如35 6+ 在遇到5后i++=2 在这次程序结束后还要自动+1 会跳过对i=2的判断  所以需要-1
        S.push(operand);
        cout << "进入operand S is:" << endl;
        Print(S);
    }


    //  cout << i << endl;
}
return S.top();

}

int main()
{
cout << "input postfix" << endl;
string expression;
// cin>>expression;
getline(cin, expression);
cout << "expression:" << expression << endl;
int result = EvaluatePostfix(expression);
cout << "result is " << result << endl;

}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment