5 replies to this topic

[yangss]

How can i solve mathematic expression wif parentheses for example (2*3)+3??

[abzero]

one classic way is to parse into a parse tree. The parentheses then only define how the tree is built.

for example:

(2*3)+3:


     +

   /   \

  *    3

/  \

2  3


(5+10)*4 :

      *

     /  \

   +    4

  / \

 5  10

Evaluation is then simple.


- I think another way is to convert into pre or post fix notation, then evalute that?

[yangss]

abzero said:

one classic way is to parse into a parse tree. The parentheses then only define how the tree is built.

for example:

(2*3)+3:


     +

   /   \

  *    3

/  \

2  3


(5+10)*4 :

      *

     /  \

   +    4

  / \

 5  10

Evaluation is then simple.


- I think another way is to convert into pre or post fix notation, then evalute that?

I never learn pre and post, and honestly im hardly can understand your explaination, im beginner in C, still fresh in many things. Any simpler ways? >.<

[abzero]

Ok, well normal notation is called infix, so

3+4+5, or 3*4+5 etc.

this is natural to read to humans, but has some issues with order of operations. For instance given this expression:
1-1-1, you can group it either as (1-1)-1, or 1-(1-1), giveing the answers of -1 or 1. So we divised all these rules to sort out the
order of the operations. etc...

Prefix notation instead puts the operator before the operands (no in the middle) so:
+ 3 4 ( == 3+4)
++2 5 6 ( == 2+5+6, specifically it equals (2+5)+6)
*+2 5 6 ( == (2*5)+6)
+*3 4 5 ( == (3*4)+5)

Postfix is similar but in reverse so
3 4 +,
3 4 5 + + (:= 5+4+3 )
3 4 5 * + (:= (5*4)+3)
etc..

Now evaluating these is easier than evaluating infix, as you can do it using a stacks. I'll give an example using prefix.
Say given this expression:

+*3 4 5

You have two stacks, the number stack and the operator stack.
Going from left to right, if you find an operator you push onto the operator stack, if you find a number you push onto the number stack;
if the number stack contains two numbers and you have an operator on the operator stack, you do the operatation and push the result onto the number stack. When the operator stack is empty, and the number stack's size is 1 your done.

So: + * 3 4 5
first token +, push on to operator stack [+] num stack []
second token *, push on to operator stack [*,+] num stack []
third token 3, push on to number stack [3], op stack [*,+]
fourth token 4, push on to number stack [4,3], op stacl [*,+]
number stack has 2 elements, pop operator stack (giving operator *, and stack [+]), pop two from number stack 4,3,
do operator, to give 12, push to num stack [12] with op stack [+]
fith token 5, push on to number stack [5,12] with op stack [+]
pop op (+) pop numbers 5,12, do operator = 17 push onto num stack [17]

This was a way calculators used to calculate numbers (although the human had to evaluate it.)

So you convert your infix into postfix/prefix then evaluate it (maybe using Shunting-yard algorithm - Wikipedia, the free encyclopedia)

[Warrior]

Here's a rough example of an expression parser it can solve (),+,*,/,%......
I haven't really tested it much so if there are some errors.....
take it as an example..

expr.c

#include "expr.h"

static int state;

int lexan()
{
    char *tmp=token;
    char c;
    *tmp=0;

    while(isspace(*pbuf))pbuf++;

    if(*pbuf==0)
        return END;

    state=0;
    while(c=*pbuf){
        switch(state)
        {
            case 0:
              if(isdigit(c))
                  state=1;
              else if(c=='.')
                  state=2;
              else c=0;
              break;
            case 1:
              if(c=='.')
                  state=2;
              else if(c=='E' || c=='e')
                  state=3;
              else if(!isdigit(c))
                  c=0;
              break;
            case 2:
              if(c=='E' || c=='e')
                  state=3;
              else if(!isdigit(c))
                  c=0;
              break;
            case 3:
              if(!isdigit(c))
                  c=0;
              break;
        }
        if(c==0)
          break;
        pbuf++;
        *tmp++=c;
    }

    if(tmp!=token){
        *tmp=0;
        return NUM;
    }

    if(strchr("+-/*%()",*pbuf)){
        *tmp++=*pbuf++;
        *tmp=0;
        return *(tmp-1);
    }
    return NONE;
}


void error(char *e)
{
    fputs(e,stdout);
    exit(1);
}


void match(int t)
{
    if(lookahead==t)
       lookahead=lexan();
    else
       error("Syntax error\n");
}


void parse(double *val)
{
    *val=0;
    lookahead=lexan();
    if(lookahead!=END)
       expr(val);
    else
       error("No character in stream\n");
}


void expr(double *val)
{
    double t;
    term(val);

    while(1){
         switch(lookahead)
        {
            case '+':
                match('+');term(&t);*val+=t;
                break;
            case '-':
                match('-');term(&t);*val-=t;
                break;
            default:
                return;
        }
    }
}


void term(double *val)
{
    double t;
    rest(val);

    while(1){
         switch(lookahead)
         {
             case '*':
                 match('*');rest(&t);*val*=t;
                 break;
             case '/':
                 match('/');rest(&t);*val/=t;
                 break;
             case '%':
                 match('%');rest(&t);*val=(int)*val%(int)t;
                 break;
             default:
                 return;
         }
    }
}

void rest(double *val)
{
    char op=0;
    if(lookahead=='+' || lookahead=='-'){
        op=lookahead;
        match(lookahead);
    }
    factor(val);
    if(op=='-')
        *val=-(*val);
}


void factor(double *val)
{
    switch(lookahead)
    {
        case '(':
             match('(');expr(val);match(')');
             break;
        case NUM:
             sscanf(token,"%lf",val);match(NUM);
             break;
        default:
             return;
    }
}


int main()
{
    fputs("Enter expression:",stdout);
    pbuf=buffer;
    fgets(pbuf,sizeof(buffer),stdin);
    parse(&value);
    printf("Value:%.2lf\n",value);
    return 0;
}

expr.h

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

#define NUM   256
#define NONE  257
#define END   258


char token[20];
int lookahead;
char buffer[100];
char *pbuf;
double value;

int lexan();
int isdelim(char);
void error(char *);
void match(int);
void parse(double *);
void expr(double *);
void term(double *);
void rest(double *);
void factor(double *);

[JCoder]

You will save yourself a lot of work if you use some parser generator. This allows for much more flexibility than hand coded parser. Doing parsers by hand is extremely error-prone.

I couldn't find a reasonable example for this in C/C++, but here is example of what I think of:

sealed abstract class Expr {
    def eval():Double
}

case class EConst(value:Double) extends Expr {
    def eval():Double = value
}

case class EAdd(left:Expr, right:Expr) extends Expr {
    def eval():Double = left.eval + right.eval
}

case class ESub(left:Expr, right:Expr) extends Expr {
    def eval():Double = left.eval - right.eval
}

case class EMul(left:Expr, right:Expr) extends Expr {
    def eval():Double = left.eval * right.eval
}

case class EDiv(left:Expr, right:Expr) extends Expr {
    def eval():Double = left.eval / right.eval
}

case class EUMinus(e:Expr) extends Expr {
    def eval():Double = -e.eval
}

import scala.util.parsing.combinator.lexical.StdLexical

class ExprLexical extends StdLexical {
    override def token: Parser[Token] = floatingToken | super.token

    def floatingToken: Parser[Token] =
        rep1(digit) ~ optFraction ~ optExponent ^^
            { case intPart ~ frac ~ exp => NumericLit(
                    (intPart mkString "") :: frac :: exp :: Nil mkString "")}

    def chr(c:Char) = elem("", ch => ch==c )
    def sign = chr('+') | chr('-')
    def optSign = opt(sign) ^^ {
        case None => ""
        case Some(sign) => sign
    }
    def fraction = '.' ~ rep(digit) ^^ {
        case dot ~ ff => dot :: (ff mkString "") :: Nil mkString ""
    }
    def optFraction = opt(fraction) ^^ {
        case None => ""
        case Some(fraction) => fraction
    }
    def exponent = (chr('e') | chr('E')) ~ optSign ~ rep1(digit) ^^ {
        case e ~ optSign ~ exp => e :: optSign :: (exp mkString "") :: Nil mkString ""
    }
    def optExponent = opt(exponent) ^^ {
        case None => ""
        case Some(exponent) => exponent
    }
}

import scala.util.parsing.combinator.syntactical._

object ExprParser extends StandardTokenParsers {
    override val lexical = new ExprLexical
    lexical.delimiters ++= List("+","-","*","/","(",")")

    def value = numericLit ^^ { s => EConst(s.toDouble) }

    def parens:Parser[Expr] = "(" ~> expr <~ ")"

    def unaryMinus:Parser[EUMinus] = "-" ~> term ^^ { EUMinus(_) }

    def term = ( value |  parens | unaryMinus )

    def binaryOp(level:Int):Parser[((Expr,Expr)=>Expr)] = {
        level match {
            case 1 =>
                "+" ^^^ { (a:Expr, b:Expr) => EAdd(a,b) } |
                "-" ^^^ { (a:Expr, b:Expr) => ESub(a,b) }
            case 2 =>
                "*" ^^^ { (a:Expr, b:Expr) => EMul(a,b) } |
                "/" ^^^ { (a:Expr, b:Expr) => EDiv(a,b) }
            case _ => throw new RuntimeException("bad precedence level "+level)
        }
    }
    val minPrec = 1
    val maxPrec = 2

    def binary(level:Int):Parser[Expr] =
        if (level>maxPrec) term
        else binary(level+1) * binaryOp(level)

    def expr = ( binary(minPrec) | term )

    def parse(s:String) = {
        val tokens = new lexical.Scanner(s)
        phrase(expr)(tokens)
    }

    def apply(s:String):Expr = {
        parse(s) match {
            case Success(tree, _) => tree
            case e: NoSuccess =>
                   throw new IllegalArgumentException("Bad syntax: "+s)
        }
    }

    def test(exprstr: String) = {
        parse(exprstr) match {
            case Success(tree, _) =>
                println("Tree: "+tree)
                val v = tree.eval()
                println("Eval: "+v)
            case e: NoSuccess => Console.err.println(e)
        }
    }
    
    //A main method for testing
    def main(args: Array[String]) = test(args(0))
}               

For C++ you would probably need to employ ANTLR or Yacc for it, but the idea is similar.