CODEWITHSUNDEEP
c++polish-notation
Gabriel Rodrigues
Gabriel Rodrigues

Reputation: 510

Calculation of Polish Expression

i'm searching for something that explains how i can calculate an Polish Expression, example:

if i have this ((1+2)*4)+3, in normal way is 1+2*4+3 = 15, but i need to write this way: 12+4*3+ to using stack getting the value of top and putting in the stack again, see my code : https://ideone.com/0bdkkM

i already see one post but i dont understand how i can make the operations required: StackOverflow

Upvotes: 0

Views: 1310

Answers (2)

Sean
Sean

Reputation: 62532

Here's a simple RPN evaluator, without any error handling. You only need a stack to store the operands, not the operators, which makes it pretty easy to implement.

Note that this version assumes the operands are single digit numbers on the input expression. I've done this to simplify parsing the RPN expression. In real life you'd want to handle multi-digit operands.

std::stack<int> stack;

const char *expression="12+4*3+";

for(char c=*expression; c!=0; c=*expression++)
{
    switch(c)
    {
        case '+':
        {
            int rhs=stack.top();    stack.pop();
            int lhs=stack.top();    stack.pop();
            int result=lhs+rhs;
            stack.push(result);
            break;
        }

        case '-':
        {
            int rhs=stack.top();    stack.pop();
            int lhs=stack.top();    stack.pop();
            int result=lhs-rhs;
            stack.push(result);
            break;
        }

        case '*':
        {
            int rhs=stack.top();    stack.pop();
            int lhs=stack.top();    stack.pop();
            int result=lhs*rhs;
            stack.push(result);
            break;
        }

        case '/':
        {
            int rhs=stack.top();    stack.pop();
            int lhs=stack.top();    stack.pop();
            int result=lhs/rhs;
            stack.push(result);
            break;
        }

        default:
            int number=(c-'0');
            stack.push(number);
            break;
    }
}

int final_result=stack.top();
std::cout << "result is " << final_result << std::endl;

Upvotes: 1

Mark Ransom
Mark Ransom

Reputation: 308452

The reason Reverse Polish became popular is because it maps nicely to the computer concept of a stack.

When the user enters a number, push it on the stack.

When the user enters an operator, pop 2 numbers from the stack, calculate the result, and push the result back on the stack.

Upvotes: 1

Related Questions