How do I write a parser in C or Objective-C without a parser generator?

Question

I am trying to make a calculator in C or Objective-C that accepts a string along the lines of

8/2+4(3*9)^2

and returns the answer 2920. I would prefer not to use a generator like Lex or Yacc, so I want to code it from the ground up. How should I go about doing this? Other than the Dragon book, are there any recommended texts that cover this subject matter?

Answer 1

Dave DeLong's DDMathParser class may save you a lot of time and trouble.

Answer 2

If I remember correctly, you can solve this problem with two stacks, one for the operators, the other for the operands.

// OPTR stack: store operators
// OPND stack: store operands
// OP: predefined set of operators
OperandType EvaluateExpression(){  

   InitStack(OPET);Push(OPTR,'#');  
   initStack(OPND);c=getchar();  
   while(c!='#'||GetTop(OPTR)!='#'){  
     if(!In(c,OP)){Push((OPND,c);c=getchar();} //Push to stack if not operator
     else 
       switch(Precede(GetTop(OPTR),c){
         //Top element in stack has a lower priority  
         case '<':
               Push(OPTR,c); c=getch();  
               break;
         case '=':
               Pop(OPTR,x); c=getch();  
               break;
         //Pop top element and push back the calculated result 
         case '>':
               Pop(OPTR,theta);  
               Pop(OPND,b); Pop(OPND,a);  
               Push(OPND,Operate(a,theta,b));  
               break;  
         } 
     } 
     return GetTop(OPND);
   }

Answer 3

The shunting yard algorithm has already been mentioned. The other classic one is simple recursive descent. Here's a fairly short one I wrote many years ago:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void expression(void);

void show(int ch) { 
    putchar(ch);
    putchar(' ');
}

int token() { 
    int ch;
    while (isspace(ch=getchar()))
        ;
    return ch;
}

void factor() { 
    int ch = token();
    if (ch == '(') {
        expression();
        ch = token();
        if (ch != ')') {
            fprintf(stderr, "Syntax error. Expected close paren, found: %c\n", ch);
            exit(EXIT_FAILURE);
        }
    }
    else
        show(ch);
}

void term() { 
    int ch;
    factor();
    ch = token();
    if (ch == '*' || ch == '/') {
        term();
        show(ch);
    }
    else
        ungetc(ch, stdin);
}

void expression() {
    int ch;
    term();
    ch = token();
    if (ch == '-' || ch=='+') {
        expression();
        show(ch);
    }
    else 
        ungetc(ch, stdin);
}

int main(int argc, char **argv) {
    expression();
    return 0;
}

Note that this particular one just parses input, and converts it to RPN form. If you want to interpret the result instead, you'd replace printing out each operand/operator with actually evaluating the result of that part of the expression.