C++ Postfix Expressions Using Stacks

Question

I'm developing a program that calculates the result of a postfix expression for one of my computer science classes. The program uses a stack ADT to accomplish this.

I have written the program, but believe there may be an error because the result of some expressions are not correct. I'm not sure where my mistake is.

Also, when the input file is empty, the program produces a value of 32767. Where is that coming from?

Expression: 3 4 + 3 * Value = 21.

Expression: 5 4 3 2 1 - + / * Value = 0. (should be 5)

Expression: 9 5 2 4 + - 2 * * Value = 18. (should be -18)

Header File:

#ifndef STACK_H #define STACK_H #include <cstdlib> #include <iostream> class Stack { public: typedef int Item; static const int CAPACITY = 50; // Constructor Stack() { used = 0; } // Modification Member Functions void push(Item entry) { data[used] = entry; ++used; } Item pop() { if(!empty()) { --used; return data[used]; } } // Constant Member Functions bool empty() const { return used == 0; } int size() const { return used; } private: // Data Members Item data[CAPACITY]; int used; }; #endif

Main Program:

#include <cstdlib> #include <iostream> #include <fstream> #include "stack.h" using namespace std; int main() { Stack s; string input; ifstream infile; int final, operand1, operand2, result; char infile_name[80]; cout << "Enter input file name: "; cin >> infile_name; cout << endl; infile.open(infile_name); while(!infile) { cout << "Could not open file." << endl; return 0; } while (!infile.eof()) { getline(infile, input); cout << "Expression: "; for (int i = 0; i < input.length(); i++) { cout << input[i]; if(input[i] == '1' || input[i] == '2' || input[i] == '3' || input[i] == '4' || input[i] == '5' || input[i] == '6' || input[i] == '7' || input[i] == '8' || input[i] == '9') s.push(input[i] - '0'); if(input[i] == '+') s.push(s.pop() + s.pop()); if(input[i] == '-') s.push(s.pop() - s.pop()); if(input[i] == '*') s.push(s.pop() * s.pop()); if(input[i] == '/') s.push(s.pop() / s.pop()); } final = s.pop(); cout << endl << "Value = " << final << "." << endl << endl; } }

why not use isdigit instead of input[i] == '1' ...

Ed Heal
– Ed Heal

2013-10-15 01:31:36 +00:00
Commented Oct 15, 2013 at 1:31 — Ed Heal
– Ed Heal, Commented Oct 15, 2013 at 1:31
Have you tried debugging it?

Raymond Chen
– Raymond Chen

2013-10-15 02:48:40 +00:00
Commented Oct 15, 2013 at 2:48 — Raymond Chen
– Raymond Chen, Commented Oct 15, 2013 at 2:48

Dave S · Accepted Answer · 2013-10-15 01:32:38Z

One issue is that in the statement s.pop() - s.pop() (and similarly in division), there is no guarantee which s.pop() is called first. As such, the order that things are removed from the stack isn't consistent. You should do it as two separate calls.

auto oper1 = s.pop(); auto oper2 = s.pop(); s.push(oper1-oper2);

Your erroneous results are due to those two operations being performed in the wrong order, in your case.

Jerry Coffin · Accepted Answer · 2013-10-15 01:37:59Z

Code like while (!infile.eof()) is virtually always an error. It will typically appear to read the last item of input twice (though even that isn't dependable).

Start by changing:

while (!infile.eof()) { getline(infile, input);

to:

while (getline(infile, input))

and see if it doesn't work better.

Also note that your stack.pop() doesn't return a value if the stack is empty:

Item pop() { if (!empty()) { --used; return data[used]; } }

If (for example) you have extra operator, you'll try to use a value when it hasn't actually returned one, leading to undefined behavior.

Collectives™ on Stack Overflow

C++ Postfix Expressions Using Stacks

2 Answers 2

Comments

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Related