Algebraic calculator algorithm

[TheWinterSnow]

Not so much hardware related but related to an AVR project that I am working on.

I have been in the process of using an ATMega2560 to make a physically functioning programmable scientific calculator.  Last semester in my programming class we built an RPN calculator in java and my professor made mention that an algebraic calculator would be difficult to make, I scoffed at that until just yesterday.

The basic operation of a scientific calculator is extremely complicated...and as I have discovered very convoluted.

There are a couple of rules I have to abide by:

- I am using a stack to hold my numbers and math functions
- The stack should be kept as small as possible and only parenthesis require more than two items on the stack
- math functions such as + - * / should act as an = but remembers to do math to the next new number

The last one is what makes things confusing, because I am trying to make a calculator that operates like a standard scientific calculator or just a standard calculator when you type 1 + 2 and then press + again, it computes the previous equation to 3 the instant you hit the second +, but remembers that it is adding the following number about to be input.  Keep in mind, the input is being done with a command terminal style setup where the code tests for the most recent input.

The problem is because I am using a command line based system, I need to know what has happened previously, and I am in a rut that looks like in order to do so I have to use a whole gambit of flags and complicated logic that seems unnecessary.

this is what I have so far, minus the functions in other files that should be self explanatory:

Code: [Select]

int main(){

char userInput[8];
double data = 0;

while(1){

// TODO Initialize LCD

// TODO while loop scans for button pressed
// sets port value to variable

// get initial user input
printf(">: ");
scanf("%s", userInput);

// First itteration, first input must be a number
// Scans until a valid number is given
while ((double)userInput[0] < 48 || (double)userInput[0] > 57){
printf(">: ");
scanf("%s", userInput);
}

// Enters 1 number into the data variable
numberEntry(userInput, &data);
printf("\n   %f", data);

// TODO while loop that polls until button depress

// scan for number or command
printf("\n>: ");
scanf("%s", userInput);

// continue loop as long as userInput is a number
while((double)userInput[0] >= 48 && (double)userInput[0] <= 57){
numberEntry(userInput, &data);
printf("   %f", data);
printf("\n>: ");
scanf("%s", userInput);
}

push(data);
data = 0;

// ---- Break out of inputing numbers to do math

// add
if(strcmp(userInput, "+") == 0){

push(pop() + data);
data = 0;
printf("   %f\n", peek());
}

// subtract
else if(strcmp(userInput, "-") == 0){
push(pop() - data);
data = 0;
printf("   %f\n", peek());
}

// multiply
else if(strcmp(userInput, "*") == 0){
push(pop() * data);
data = 0;
printf("   %f\n", peek());
}

// divide
else if(strcmp(userInput, "/") == 0){
push(pop() / data);
printf("   %f\n", peek());
}

else if(strcmp(userInput, "clr") == 0){
first = null;
data = 0;
printf("   %f\n", peek());
}
}

return 0;
}

obviously this code doesn't work, it pulls a zeros from the stack and adds that.  I am at a loss here,  if anyone could fill me in for some better topologies that would be great.

I am looking into making the basic calculator and the hardware open source so that people that build their own scientific calculator, getting the input to work like a classical sceintific calculator would be the biggest breakthrough o f the project.

BIG NOTE: If it hasn't seemed obvious I am trying to code in C language for PC just to get a working prototype and once I works will modify the code to work for embedded systems, hence why you see stdio.h and stdlib.h functions and console displays.

[rs20]

So one immediate point. Rewrite

Code: [Select]

while ((double)userInput[0] < 48 || (double)userInput[0] > 57){As

Code: [Select]

while (userInput[0] < '0' || userInput[0] > '9'){
No need to cast it to a double, nor cryptically use ASCII codes.

But the main thing you need to do is to define what behaviour you actually want, because I'm not familiar with the sort of calculator your talking about. Not just so that we know what you want, but the act of specifying the behaviour you want in a precise and systematic way is half the task of coding it even if you're doing it by yourself. "Just a standard calculator" is horrendously vague.

So what is the screen supposed to say after I've typed "5*7+3*"? And what is it supposed to say after I've typed "5*7+3*2="? 41 or 76? Your standard 4-banger will say 76, an S-VPAM will say 41.

[IanB]

Traditional scientific calculators that respond immediately to key presses have an X and a Y register. The X register is hidden and the Y register appears on the display. When you enter a value it is shifted into the Y register. If you press a binary operator key like + or * the value in the Y register is copied into the X register, the operation is stored, and the Y register is set to accept a new entry. If you then press another binary operator key then the X and Y registers are combined using the stored pending operator, the result is placed in the X register, the key press is stored as a new pending operator, and the Y register is reset to accept a new entry. There are variations around this for the = key (a no-op), for example.

If the calculator handles arithmetic precedence then the X register becomes a number stack and the pending operation register also becomes a stack. Pushing or unwinding the stack now depends on the relative precedence of the key presses and what is on the stack.

(Unary operators such as sin or sqrt simply replace the contents of the Y register with the result, leaving the X register and the stack untouched.)

[rs20]

Yes, assuming the OP wants the "Immediate execution" Calculator Input Method, IanB's description is right. Of course, even with immediate execution, you need a larger stack to handle brackets, and the OP clearly had this in mind with "The stack should be kept as small as possible and only parenthesis require more than two items on the stack". So, i.e, only 2 items on the stack.

TheWinterSnow: I think you're getting yourself tangled up dealing with the special case of the first input number. I mean, clearly your code is trying to consume two numbers before consuming the first math operator. Obviously the math operator should be consumed between the two numbers. If I were you, I would make it so that the variables were initialized as if you're halfway through a formula, and get it to work correctly starting from that point. Then add your initial special case. Start by writing pseudocode if you think that'll help. But you have to read in the math operator before you read in the second number.

[atferrari]

Wouldn't a flow diagram be of help here? 

I use it always, because, first of all, it helps me to have a clear idea of what the algorithm should be.

Then, writing code seems more a clerical task.

[amyk]

If you ignore precedence and parens and just do everything sequentially then the algorithm of which IanB has explained will suffice; but if you want to handle parentheses and have the correct precedences, then you'll need some algorithm like this:
https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm

Here is a very minimal implementation of this technique; it's a C compiler but contains the expression parser that's relevant:
https://github.com/rswier/c4/blob/master/c4.c

If you happen to know x86 asm, this may also interest you:
http://www.hugi.scene.org/compo/compoold.htm#compo4

[IanB]

Recursive descent parsing does indeed work very well for "algebraic entry" calculators, but the alternative, stack-based approach that I outlined is possibly more convenient for "immediate response" calculators.

I implemented such an algorithm based on a reference that I read many years ago. It would take me more time than I have available now to describe the algorithm in detail, but maybe I can summarize it later. It will handle precedence ordering, parentheses and mathematical functions in the expected way and is not limited to pure sequential evaluation.

[jolshefsky]

Let me make use of my computer science degree minted in 1993 ...

I would take a look at the problem from a binary tree perspective and work from there to make optimizations. I would also keep in mind what to do with erroneous input (e.g. "3 * - 5": does that mean "multiply-I-meant-subtract" or "multiply by minus 5"?)

For the binary tree, you can represent all the two-parameter operations (add, divide, etc. versus cosine or square root) in it where any node can either be a number or an operator that has two children. You can then traverse the tree to generate prefix, infix, or postfix notation (where you output a node when it is first visited, between its children, or after all its children have been visited.) For instance:

3 * 4 + 5 * 8 would make a tree like:

Code: [Select]

       +
  *         *
3   4    5   8
Traversing postfix yields the children first, so you'd get 3 4 * 5 8 * + and you're back to the easy RPN functionality.

The trick, so-to-speak, is to collapse the tree as soon as you can get an answer. So 3 * 4 + can immediately be collapsed to (the equivalent) 12 +. "12 + 5 *" is tricky because you need a tree portion that is the whole expression because you need to wait for 5 * 8 until you can get 40 then 12 + 40 = 52. Parentheses just force the tree into an order-of-operations that is non-natural (e.g. "( 12 + 5 ) * 8" builds a different tree, but the closing parenthesis collapses "12+5").

In conclusion, let me say that infix notation is stupid and ambiguous and I hate it. 

[miguelvp]

I made an in program compiler that would translate an algebraic formula into 8087 machine language. Pretty much doing the same thing as jolshefsky suggests, I would build the tree while interpreting the equation so in effect converting it to RPN, which suited the math coprocessor.

I'll check if I still have that code, but it's old (30 years ago) but the ending program still works in dos box. I'll put a screenshot if I can run it here at work.

My brother did the program I only did the compiler but it made it way way faster since he was interpreting the formula per iteration.

[senso]

Take a look on this PIC32 based calculator:
http://www.gabotronics.com/product-info/design-coma.htm

[miguelvp]

Found the executable and it works. I'll check if I can find the code, CGA graphics, did support Hercules and maybe EGA not sure.



Take into account this is 30 years old and the code is really not that well written.

[IanB]

3 * 4 + 5 * 8 would make a tree like:

Code: [Select]
       +
  *         *
3   4    5   8

Traversing postfix yields the children first, so you'd get 3 4 * 5 8 * + and you're back to the easy RPN functionality.

The trick, so-to-speak, is to collapse the tree as soon as you can get an answer. So 3 * 4 + can immediately be collapsed to (the equivalent) 12 +. "12 + 5 *" is tricky because you need a tree portion that is the whole expression because you need to wait for 5 * 8 until you can get 40 then 12 + 40 = 52. Parentheses just force the tree into an order-of-operations that is non-natural (e.g. "( 12 + 5 ) * 8" builds a different tree, but the closing parenthesis collapses "12+5").

Here's an example of how to do stack based evaluation in immediate mode as with old style calculators.

Given the expression "3 * 4 + 5 * 8 =", the evolution of the stacks goes like this:

Enter: 3
Number stack: 3
Operator stack: (empty)

Enter: *
Number stack: 3
Operator stack: *

Enter: 4
Number stack: 4 3
Operator stack: *

Enter: +
Number stack: 12
Operator stack: +

Note: + has lower precedence than * so it forces the existing operator stack to be evaluated before + is pushed on
=> pop *, pop 4, pop 3, evaluate 3 * 4, push 12
=> push +

Enter: 5
Number stack: 5 12
Operator stack: +

Enter: *
Number stack: 5 12
Operator stack: * +

Note: * has a higher precedence than + so it gets pushed on the stack.

Enter: 8
Number stack: 8 5 12
Operator stack: * +

Enter: =
Number stack: 52
Operator stack: (empty)

Note: entering = causes the whole operator stack to be evaluated
=> pop *, pop 8, pop 5, evaluate 5 * 8, push 40
=> pop +, pop 40, pop 12, evaluate 12 + 40, push 52
----

An expression with parentheses, for example "5 * (4 + 3) - 1 =":

Enter: 5
Number stack: 5
Operator stack: (empty)

Enter: *
Number stack: 5
Operator stack: *

Enter: (
Number stack: 5
Operator stack: ( *

Enter: 4
Number stack: 4 5
Operator stack: ( *

Enter: +
Number stack: 4 5
Operator stack: + ( *

Enter: 3
Number stack: 3 4 5
Operator stack: + ( *

Enter: )
Number stack: 7 5
Operator stack: *

Note: a closing parenthesis causes the operator stack to be unwound down to the matching open parenthesis.
=> pop +, pop 3, pop 4, evaluate 4 + 3, push 7
=> pop (, discard it

Enter: -
Number stack: 35
Operator stack: -

Enter: 1
Number stack: 1 35
Operator stack: -

Enter: =
Number stack: 34
Operator stack: (empty)

[TheWinterSnow]

3 * 4 + 5 * 8 would make a tree like:

Code: [Select]
       +
  *         *
3   4    5   8

Traversing postfix yields the children first, so you'd get 3 4 * 5 8 * + and you're back to the easy RPN functionality.

The trick, so-to-speak, is to collapse the tree as soon as you can get an answer. So 3 * 4 + can immediately be collapsed to (the equivalent) 12 +. "12 + 5 *" is tricky because you need a tree portion that is the whole expression because you need to wait for 5 * 8 until you can get 40 then 12 + 40 = 52. Parentheses just force the tree into an order-of-operations that is non-natural (e.g. "( 12 + 5 ) * 8" builds a different tree, but the closing parenthesis collapses "12+5").

Here's an example of how to do stack based evaluation in immediate mode as with old style calculators.

Given the expression "3 * 4 + 5 * 8 =", the evolution of the stacks goes like this:

Enter: 3
Number stack: 3
Operator stack: (empty)

Enter: *
Number stack: 3
Operator stack: *

Enter: 4
Number stack: 4 3
Operator stack: *

Enter: +
Number stack: 12
Operator stack: +

Note: + has lower precedence than * so it forces the existing operator stack to be evaluated before + is pushed on
=> pop *, pop 4, pop 3, evaluate 4 * 3, push 12

Enter: 5
Number stack: 5 12
Operator stack: +

Enter: *
Number stack: 5 12
Operator stack: * +

Note: * has a higher precedence than + so it gets pushed on the stack.

Enter: 8
Number stack: 8 5 12
Operator stack: * +

Enter: =
Number stack: 52
Operator stack: (empty)

Note: entering = causes the whole operator stack to be evaluated
=> pop *, pop 8, pop 5, evaluate 8 * 5, push 40
=> pop +, pop 40, pop 12, evaluate 40 + 12, push 52
----

An expression with parentheses, for example "5 * (4 + 3) - 1 =":

Enter: 5
Number stack: 5
Operator stack: (empty)

Enter: *
Number stack: 5
Operator stack: *

Enter: (
Number stack: 5
Operator stack: ( *

Enter: 4
Number stack: 4 5
Operator stack: ( *

Enter: +
Number stack: 4 5
Operator stack: + ( *

Enter: 3
Number stack: 3 4 5
Operator stack: + ( *

Note: a closing parenthesis causes the operator stack to be unwound down to the matching open parenthesis.

Enter: )
Number stack: 7 5
Operator stack: *

Enter: -
Number stack: 35
Operator stack: -

Enter: 1
Number stack: 1 35
Operator stack: -

Enter: =
Number stack: 34
Operator stack: (empty)

I got your first post down and got a basic + - * / program working but now this one quoted has me scratching my head a little bit.  I don't want to get convoluted with unnecessary logic so I will just ask, what it the most simplistic way to determine order of precedence when are just loading ASCII values '+' '-' '*' '/' '(' ')'?  In my final iteration of the code when it gets embedded to the hardware format I planned on using integers mapped out to specific math functions but even then what is the determining factor on precedence considering that it changes when you are using parenthesis?

I am not asking to write the code for me, but rather, how do you go about setting yourself up for the task.  At this point this project is over my head and as a result I am trying to come up with more complicated solutions than are needed.

[IanB]

Precedence can be coded as an integer value.

Something like this:

*   2
/   2
+  1
-   1
(   0

Then you just compare integer values using greater than or less than.

If any new operator has lower or equal precedence than the operator on top of the stack it forces the stack to be evaluated until it is empty or until a '(' is reached.

'(' gets a precedence of 0 since any binary operator will get stacked on top of it.

If you include mathematical operators like 'sin' or 'sqrt' they operate immediately on the number at the top of the number stack and cause that value to be replaced with the result.

Also note that calculators have a '+/-' key for entering negative values so there is no confusion with the '-' key for subtraction.

[IanB]

what is the determining factor on precedence considering that it changes when you are using parenthesis?

Actually, precedence doesn't change when using parentheses. Parentheses merely have the effect of grouping certain operations together so they happen in a different order.

[TheWinterSnow]

what is the determining factor on precedence considering that it changes when you are using parenthesis?

Actually, precedence doesn't change when using parentheses. Parentheses merely have the effect of grouping certain operations together so they happen in a different order.

That is what I meant, that if you have z * (x + y), the x+y comes first, as oppossed to z * x + y  where z * x will be executed first, if the precendence of x + y is lower by some integer value, how do you go about overriding the fact that you have a * in the stack?

[IanB]

That is what I meant, that if you have z * (x + y), the x+y comes first, as oppossed to z * x + y  where z * x will be executed first, if the precendence of x + y is lower by some integer value, how do you go about overriding the fact that you have a * in the stack?

I showed you in my second example; read it carefully.

[legacy]

in this topic I have linked a toy-project I did. It contains an interpreter plus a little calculator, and it's C and C++ source. Feel free to study, and to improve, and … let me know any progress (if you want). Actually that project is in its dead-line, I am coding a new interpreter with a completely different approach.

[TheWinterSnow]

That is what I meant, that if you have z * (x + y), the x+y comes first, as oppossed to z * x + y  where z * x will be executed first, if the precendence of x + y is lower by some integer value, how do you go about overriding the fact that you have a * in the stack?

I showed you in my second example; read it carefully.

Thanks, I really have fried my brain on this project, I was confusing your first post with your second.  I think its time a step away from this project for a bout a week or so.

in this topic I have linked a toy-project I did. It contains an interpreter plus a little calculator, and it's C and C++ source. Feel free to study, and to improve, and … let me know any progress (if you want). Actually that project is in its dead-line, I am coding a new interpreter with a completely different approach.

An compiler seems like to be the best option in the long run.  I think for now I am just going to go without functions and have very simple predefined equations on a simple stack based interpreter mentioned over on the first page. 

I would like to learn Lex and Yacc, JavaCC, and AST but that is so over my head at the moment.  At the moment I am just using an ATMega 2560 to replicate my TI-36X that I can add extra functions as needed.  Once I gain the computing knowledge to add more functions, I will move to an ARM solution with mentioned compiler setup when I can get my head around said concepts.

[mushroom]

Not sure it will fit your needs, but you could consider this : http://www.codeproject.com/Articles/6877/Simple-x-Numerical-Formula-Parser

The sources are easy to read/understand/port. There are some bugs I reported to the author, but I don't know if they where fixed in the sources. Just go down to "Comments and Discussions", you will find the fixes.

[ale500]

Parsing algebraic expression can be accomplished several ways. It all depend on what do you want to do with the parsed data. If you are just evaluating numbers, a recursive algorithm is probably the simplest of the bunch. Immediate execution is also a good idea, and shouldn't be much more difficult. We learned immediate execution at school, in math classes, I mean. it is kind of intuitive, I guess.

I am after a similar goal and decided, long ago, that a binary tree would be the best because I'd like a grapher and a solver too .

If you want some advice regarding the embedded development, I'd suggest you build a library you can compile and test on your pc (Unit Tests save the day, you can see where you broke something...). When that works, go for a uC. Use static data, avoid printf (except for debug) and dynamic memory altogether and you will be mostly on the safe side .
One note: x86, Cortex-Mx allow for unaligned accesses, MIPS (PIC32) doesn't ! (learned the hard way a while ago...). Aligned accesses are faster anyways so try to use them .

Edit: I forgot another thing you have to do without (*): floating point !, specially double.
* AVR had only support for float, it is emulated anyways. The Cortex-M4 has built-in float support. There are emulation libraries, you may want to look at gcc, the sources, it had double support, code to emulate I mean.

If you want to go for one of the best alternatives, I'd suggest you look at bc. It is a unix command, it implements arbitrary-precision, like the TI-92 .
IBM produced something called decNumber, it is a library, sadly it uses malloc, but it may help you. It is what is being used for the WP-34 , something you definitely may want to look at.

[ale500]

I know it is not C and it may have some bugs , but it seems to work  . An immediate execution (kind of) algebraic to postfix AKA RPN

Code: [Select]

#!/usr/bin/python


# simple formula parser
# dictionary for the precedence
precedence = dict( [('+', 5), ('-', 5), ('*', 6), ('/', 6)] )

stack = []

def push(arg):
    if arg != ' ': # spacers represent argument that are already on the stack
        stack.append(arg)

def isNumber(tok):
    try:
        n = int(tok)
    except:
        return False
    return True

def isOp(tok):
    if tok in '+-*/':
        return True
    return False

# searches to the right of the current position for an operand with higher precedence
# it stops if finds a parenthesis or end
#
# 3 + 5 * 2 should give *
# 3 + 6 + 7 should give the first +
#
def searchToTheRight(formula, start, end):
    best = -1 # nothing found
    for i in range(start, end):
        if isOp(formula[i]):
            if best != -1:
                if precedence[formula[i]] > precedence[formula[best]]:
                    best = i
            else:
                best = i
    return best
   
# use a list of arguments to simplify

# possible parenthesis
def isParenOrFunc(tok):
    return tok in [ '(', 'sin(', 'cos(', 'tan(' ]
def isFunc(tok):
    return tok in [ 'sin(', 'cos(', 'tan(' ]

def parseFormula(formula):
    left = None
    right = None
    operator = None
   
    lformula = formula # it is going to be reduced
   
    finished = False
   
    while finished == False:
        print 'Parsing: ' + str(lformula)
        size = len(lformula)
        # search for right-most '('
        lparen = -1 # no parenthesis or function found
        rparen = -1
        for idx in range(size):
            if isParenOrFunc(lformula[idx]):
                lparen = idx
            elif lformula[idx] == ')':
                # we found it...
                rparen = idx
                break
   
        if lparen == -1:
            start = 0
            func = None
        else:
            start = lparen + 1
            func = lformula[lparen]
        if rparen == -1:
            end = size - 1
        else:
            end = rparen - 1
       
        if lparen != -1 and rparen == -1:
            print "Error: mismatched () pairs"
            quit()
   
        if start > end: #
            finished = True
            print "Finished: Empty expression"
            break

        if start - end == 0: # one number only
            print 'start - end = 0'
            if lformula[start] == ' ':
                finished = True
                print "Finished: Empty expression"
                break
            push(lformula[start]) # push number
            if isFunc(func):
                push(lformula[start]) # push to stack
            lformula[start] = ' ' # spacer
            print lformula, lparen, rparen
            if rparen != -1:
                del lformula[rparen]
            if lparen != -1:
                del lformula[lparen]
        else:
            # search for operand with highest precedence
            print 'start - end > 0'
            op = searchToTheRight(lformula, start, end)
            if op == -1:
                print 'Error: no operand'
                quit()
           
            if op == start:
                print 'Error: no left operand'
                quit()
            if op == end:
                print 'Error: no right operand'
                quit()
               
            push(lformula[op - 1])
            push(lformula[op + 1])
            push(lformula[op]) # operand
           
            if (start - 1 == lparen) and (end + 1 == rparen): # there was only one expression
                if isFunc(func):
                    push(func) # push to stack
                del lformula[rparen] # rparen
                del lformula[op + 1]
                del lformula[op]
                del lformula[op - 1]
                lformula[lparen] = ' '
            else:
                del lformula[op + 1]
                del lformula[op]
                lformula[op - 1] = ' '
               
# Tests

parseFormula([ '3' ])
print 'Stack ' + str(stack) + '\n'
stack = []
parseFormula([ '3', '+', '4' ])
print 'Stack ' + str(stack) + '\n'
stack = []
parseFormula([ '3', '+', '4', '*', '5' ])
print 'Stack ' + str(stack) + '\n'
stack = []
parseFormula([ '(', '3', '+', '4', ')'])
print 'Stack ' + str(stack) + '\n'
stack = []
parseFormula([ '4', '*', '(', '3', '+', '4', ')'])
print 'Stack ' + str(stack) + '\n'
stack = []
parseFormula([ '4', '*', '(', '3', '+', '4', ')', '*', '6'])
print 'Stack ' + str(stack) + '\n'
stack = []
parseFormula([ 'sin(', '3', '+', '4', ')', '*', '6'])
print 'Stack ' + str(stack) + '\n'
stack = []



Code: [Select]

Parsing: ['3']
start - end = 0
[' '] -1 -1
Parsing: [' ']
start - end = 0
Finished: Empty expression
Stack ['3']

Parsing: ['3', '+', '4']
start - end > 0
Parsing: [' ']
start - end = 0
Finished: Empty expression
Stack ['3', '4', '+']

Parsing: ['3', '+', '4', '*', '5']
start - end > 0
Parsing: ['3', '+', ' ']
start - end > 0
Parsing: [' ']
start - end = 0
Finished: Empty expression
Stack ['4', '5', '*', '3', '+']

Parsing: ['(', '3', '+', '4', ')']
start - end > 0
Parsing: [' ']
start - end = 0
Finished: Empty expression
Stack ['3', '4', '+']

Parsing: ['4', '*', '(', '3', '+', '4', ')']
start - end > 0
Parsing: ['4', '*', ' ']
start - end > 0
Parsing: [' ']
start - end = 0
Finished: Empty expression
Stack ['3', '4', '+', '4', '*']

Parsing: ['4', '*', '(', '3', '+', '4', ')', '*', '6']
start - end > 0
Parsing: ['4', '*', ' ', '*', '6']
start - end > 0
Parsing: [' ', '*', '6']
start - end > 0
Parsing: [' ']
start - end = 0
Finished: Empty expression
Stack ['3', '4', '+', '4', '*', '6', '*']

Parsing: ['sin(', '3', '+', '4', ')', '*', '6']
start - end > 0
Parsing: [' ', '*', '6']
start - end > 0
Parsing: [' ']
start - end = 0
Finished: Empty expression
Stack ['3', '4', '+', 'sin(', '6', '*']


[TheWinterSnow]

If any new operator has lower or equal precedence than the operator on top of the stack it forces the stack to be evaluated until it is empty or until a '(' is reached.

'(' gets a precedence of 0 since any binary operator will get stacked on top of it.

This has me a little confused here.  If I already have a multiplication on the top of the operator stack and I input an addition, the operator stack will execute the multiplication (Ex:  5 * 3 + gets executed to 15 +).  But now you say that '(' gets a precedence of 0 so 5 * ( would cause the stack to evaluate the multiplication since it has higher precedence than the '('.

Anyway I managed to get it working without the parentheses needing precedence.  I haven't added unary operators yet like sqrt() and trig functions but the hardest part is behind me.

Here is the rough code, I know it probably horribly inefficient.  I temporarily moved over to java as I thought it would be easier to work out the function of the program.  I have a feeling it's pretty crusty so any recommendations or pointers would be great.

Code: [Select]

while(true){
while(!input.equals("=")){
System.out.print("> ");

input = getInput(); // get number

// if input is "(" instead of number
if(input.equals("(")){

// continue op.push() for additional "("
while(input.equals("(")){
op.push(input); // push operator to op stack
System.out.print("> ");
input = getInput();
}

num.push(input);
}

// input is a number
else {
num.push(input); // push number to num stack
}

System.out.print("> ");
input = getInput(); // get operator

if(!input.equals("=")){
if(input.equals(")")){
while(input.equals(")")){
//unwind the stack until the next "("
while(!op.peek().equals("(")){
num.push(doMath());
}
op.pop(); // pops ooff the finished "("
System.out.print("> ");
input = getInput();
}
}
else{
precedence = getPrec(input); // precedence == newest operator
if(precedence <= getPrec(op.peek())){ // getPrec(op.peek()) == older operator

// do the operation currently in the stack
num.push(doMath());
op.push(input);
}
else {
// push the new operator onto the stack
op.push(input); // push operator to op stack
}
}
}
}

// ties up loose ends
while(!op.isEmpty()){
num.push(doMath());
}

System.out.println("> Final Result: " + num.pop());
input = "";
}

[IanB]

This has me a little confused here.  If I already have a multiplication on the top of the operator stack and I input an addition, the operator stack will execute the multiplication (Ex:  5 * 3 + gets executed to 15 +).  But now you say that '(' gets a precedence of 0 so 5 * ( would cause the stack to evaluate the multiplication since it has higher precedence than the '('.

When '(' is encountered it is always pushed onto the operator stack. It never triggers evaluation itself.

[TheWinterSnow]

That is what I did in my code.