How to get started with my stack?

[jetm0t0]

So I need to write 2 functions using the standard stack container called evaluateInfix() and infixToPostfix() that will return the result of a math equation but internally to that function it will convert this math from infix to postfix. I keep thinking I need to define my own grammar here? but I may be getting that confused with the 2nd assignment where we make our own stack class?

Anyways, if I don't need my own grammar. The rest of the description is:

Consider simple infix expressions that consist of single-digit operands; the operators +, –, *, and /; and parentheses.
Assume that unary operators are illegal and that the expression contains no embedded spaces. Design and implement the two functions mentioned above. You must first convert the infix expression to postfix form and then evaluate the resulting postfix expression.

I guess I am unsure where I will be doing the actual math, can C++ work directly on math in postfix form? If so I have not seen an example of coding that from my book. If true this would mean I can do my math work after the infixToPostfix() function.

The other part tricky part is just using push() to check for the right usage of '( )'. Really I should be able to write the logic by just understanding every rule of PEMDAS, and making sure I don't miss anything.

[jetm0t0]

I think I have a better idea on how to convert, the examples I saw in class used a switch statement. So instead of trying to use if statements with comparisons < > or == (which I am not sure you could do on operators) you can simply make a case by case situation in order of operation, so that the right math will come out.

[jonnin]

postfix makes math more simple; the postfix calculators (called reverse polish) cut the number of button mashes by 1/3 or so as an example.

the general rule of the day is pop the stack until you get an operator, perform the operation, and push the result back on the stack, repeat until stack has 1 value left.

eg for simple things,
3+3 is
3 3 +
and you end up with 6 -- one value left in the stack means you are done.

or more complex
(3+5)*2
is
3 5 + 2 *
3 5 + is 8, pushed back
8 2 *
8 2 * is 16, done...

[jetm0t0]

But you can't compare two operators right? if ("current operator" < * ) ??

[mbozzi]

This is a syntax error:
if (current_operator == +)
But this is fine:
if (current_operator == '+')

The user's input is a string. To handle this you'll make a choice to perform addition if the user typed in the character "+".

[jetm0t0]

Ok so then the only thing I would have to do in the end is convert the numbers in the string to ints to do the math? I'm not very good at that.

[jonnin]

c++ has many ways to convert text to values.
atoi and atof (to int, to decimal) for C style strings or
stoi and stod for c++ strings are two of the most simple ones.

the hard part here is converting to postfix.
you don't actually do operator precedence: its done for you by generating the postfix correctly, not in special cases -- as per my multiply a sum example. Infix to postfix is well known, you can look up how to do it. Parsing the equations can get complex, but I suspect you are just doing +-*/ here, right? If you need weird stuff like unary minus or trig or whatever else, say so.

[jetm0t0]

Oh right I used stoi in the past and it was very useful. I've got most my code written, but my output looks like this: 1*4(+3+1
when this is my input: 1+3+(4*1)

I think I am correctly deleting the old string and concatenating for a new format with this

	infixToPost.clear();

	//append to postfix the remaining operators in the stack
	while (!myStack.empty())
	{
		infixToPost += myStack.top();
		myStack.pop();
	}

But it isn't moving the operators correctly I think. I'm surprised my pseudo code to code doesn't seem to translate it correctly to postfix. Maybe I need to write a display function to properly handle the data backwards?

Oh I see now. What I have written so far only addresses if it was a valid equation. Uhg.

[seeplus]

There are basically 2 methods of converting infix to postfix - 'Shunting Yard' or 'Recursive Descent'. What is the algorithm you're using for the conversion?

single-digit operands; the operators +, –, *, and /; and parentheses.

This makes parsing the input string easier as each token is a single character. It also seems that you're dealing here only with single-digit numbers - with no variable names? Again, this makes things easier as the conversion from a digit as a char to an arithmetic number is trivial (subtract '0').

I've got most my code written

If you post your code, then we'll be able to advice/comment in more detail.

[jetm0t0]

Ya I got it figured out. I spent a long time debugging and noticed it wasn't even entering my complex while loop condition. I kind of ignored what I didn't realize was a helper function called precedence(). Because the ASCII table is your friend and I forgot that "1" is a higher value than "+". I assumed it was all digits first and then the operators but the ascii table has operators not in contiguous values. Anyways, once I realized I needed to specify a precedence int value for each condition either a + , - or *, / then I could compare like the pseudo code was showing me. Then I just spent all day trying to find why the last character wasn't printed, and I had two different char variables in the new function I made, and wasn't doing anything with the variable I needed, so that was a dumb dumb moment.

I'm just making the evaluation function now.

Is there any major difference between pre and postfix? I was confused as if they were very different, and not mainly just another way to translate the math. I did read on google that it's easier on the computer to convert a pre to post or vice versa, rather than trying to convert from an infix.

[jonnin]

the terms pre, post, and in fix come from the tree structure.

if you had a small tree,

   +
  /  \
  1  2

all that changes here is the root node's processing order. The names are based off that, so its either first (pre), last (post), or in the middle (in).

in order then is 1 + 2 or left, root, right
preorder is root first, + 1 2
and postorder is left, right, root or 1 2 +

trees are aggravating and inefficient: you will note that c++ does not provide one directly in the container library, and for a reason. But they are critical for visualizing some kinds of problems. The equation parsing that you are doing comes from drawing it as a tree, but is more efficiently done directly once the algorithm pops out at you. Note that the postorder traversal is exactly how you put it into a RPN calculator.

[jetm0t0]

Ah ok. So now I am stuck, trying to write logic to add it all up. I finally got:
13+41*+ which should be correct postfix for 1+3+(4*1). But I totally forgot the parentheses got removed during infixToPost function. So I can't just copy the logic I wrote earlier. I am drawing a blank on how to properly calculate it all...

I forgot, That's the point of postfix. The code examples I saw are crashing my program. I think because it doesn't like trying to add two operands and return that value to a stack. Idk...

[mbozzi]

Here's an example of how to evaluate RPN:

#include <iostream>

struct token
{ 
  union { double x; char o; };
  bool is_number;   
  token(double x): x(x), is_number(true) {}
  token(char o): o(o), is_number(false) {} 
};

int main()
{    
  token expr[] = { 1.0, 3.0, '+', 4.0, 1.0, '*', '+' };
    
  token const* const begin = expr;
  token const* const end = expr + (sizeof(expr) / sizeof(*expr)); 
  token* next = expr;
  token* top  = expr;
    
  struct underflow_exception {}; 
  auto const pop_operand = [&]{ return top == begin? throw underflow_exception{}: (--top)->x; }; 
    
  for ( ;; ++next, ++top )
  {
    while (next != end && next->is_number) *top++ = *next++; 
    if (next == end) break;
  
    double const op2 = pop_operand();
    double const op1 = pop_operand();

    if (next->o == '/') *top = op1 / op2;
    if (next->o == '+') *top = op1 + op2;
    if (next->o == '-') *top = op1 - op2;
    if (next->o == '*') *top = op1 * op2;
  }
    
  std::cout << std::fixed << pop_operand() << '\n';
}

[jetm0t0]

Ya that's basically the same code I keep seeing. My bad for the confusion. I have dyslexia, and I totally put a bool return in there somehow because a previous example in the book was going over "balanced" expressions or equations. So now I know the instructions assumed we have it in the right form, it was only asking to manipulate a string and a stack. No need for a bool and that's why the code was crashing because the evaluateInfix() had no actual string to work with.

And thanks for that last example. I realized I need to use doubles not ints, because 5 / 3 isn't a pretty whole number, so he might dock points for missing 1 or 2 decimals.