A Calculator Supports Parentheses Writtren in C

 The flow chart be:

 Read Input  -> Get Tokens -> Infix To Postfix -> Evaluate -> Output Result



GetToken : Check if there are the known syntaxes or not.

Infix To Postfix: Check if the parentheses are balance or not.

Evaluate: Check if there is the operator or operand being dangle or not.


My Code:

/*
ref :
 http://www.paulgriffiths.net/program/c/calc1.php
 http://openhome.cc/Gossip/AlgorithmGossip/InFixPostfix.htm //tranditional chinese
*/


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

#include <ctype.h>
#include <math.h>

#define _FORCE_FLOATING_ARITHMETIC

#ifndef FALSE
 #define FALSE       (0)
 #define TRUE       (1)
#endif

#define MAX_STR_LEN       (256)

enum TokenType
{
 Unknown,
 ExpressionEnd,
 Operator,
 OperandInteger, OperandFloat
};

enum OperatorType
{
 OP_UNKOWN = 0, OP_PLUS, OP_MINUS, OP_MULTIPLY, OP_DIVIDE,
 OP_POWER, OP_MOD, OP_LPAREN, OP_RPAREN, 
};

typedef struct TokenProperty {
 enum TokenType tokenType;

 union
 {
  long long intValue;
  double floatValue;
  struct
  {
   enum OperatorType operatorType;
   char unknownSymbol;
  };
 };/*union*/
}TokenProperty;


int GetTokenNumber(char *pStr, int bufferSize)
{
 int number;
 char *pMovBuf;

 number = 0;
 pMovBuf = pStr;
 while ((pMovBuf - pStr) < bufferSize)
 {
  char *pTemp;

  if ('\0' == *pMovBuf || '\n' == *pMovBuf || EOF == *pMovBuf)
  {
   number++;
   break;
  }/*if end */

  if (isspace(*pMovBuf))
   pMovBuf++;

  pTemp = pMovBuf;

  strtold(pMovBuf, &pTemp);

  if (pMovBuf == pTemp
   || *pTemp == 'e' || *pTemp == 'E'
#if(0)
   || *pTemp == 'f' || *pTemp == 'F'
#endif
   )
  {
   pTemp++;
  }/*if strtold valid or float suffix*/

  pMovBuf = pTemp;
  number++;
 }/*while 0 < bufferSize*/

 return number;
}/*GetTokenNumber*/


int PrintTokenProperty(int n, struct TokenProperty *pTokens)
{
 int i;

 for (i = 0; i < n; i++) {
  switch (pTokens[i].tokenType)
  {
  case Unknown:
   printf("Unknown\n");
   break;
  case ExpressionEnd:
   printf("ExpressionEnd\n");
   break;
  case Operator:
   printf("Operator, ");
   switch (pTokens[i].operatorType)
   {
   case OP_UNKOWN:
    printf("OP_UNKOWN \n");
    break;

   case OP_PLUS:
    printf("OP_PLUS \n");
    break;
   
   case OP_MINUS:
    printf("OP_MINUS \n");
    break;

   case OP_MULTIPLY:
    printf("OP_MULTIPLY \n");
    break;

   case OP_DIVIDE:
    printf("OP_DIVIDE \n");
    break;

   case OP_POWER:
    printf("OP_POWER \n");
    break;

   case OP_MOD:
    printf("OP_MOD \n");
    break;

   case OP_LPAREN:
    printf("OP_LPAREN \n");
    break;

   case OP_RPAREN:
    printf("OP_RPAREN \n");
    break;

   default:
    return -2;
   }/*switch operatorType*/
   break;
  case OperandInteger:
   printf("OperandInteger, %lld\n", pTokens[i].intValue);
   break;
  case OperandFloat:
   printf("OperandFloat, %f\n", pTokens[i].floatValue);
   break;
  default:
   return -1;
  }/*switch tokenType*/

 }/*for */
 printf("\n");
 return 0;
}/*PrintTokenProperty*/


int GetNextToken(char *pStr, int strSize, struct TokenProperty *pToken, int *pCostedStrLen)
{
 int tokenLen;
 char *pMovBuf;

 tokenLen = 0;
 pMovBuf = pStr;


 if ('\0' == *pMovBuf || '\n' == *pMovBuf || EOF == *pMovBuf)
 {
  pToken->tokenType = ExpressionEnd;
  pMovBuf++;
  goto Flag_End_GetToken;
 }/*if*/

 while (*pMovBuf && isspace(*pMovBuf))
  pMovBuf++;

 if (FALSE != isdigit(*pMovBuf))
 {
  /*  Token is an operand  */
  int isFloat;
  isFloat = FALSE;

  {
   long long intValue;
   char *pTemp;

   intValue = strtoll(pMovBuf, &pTemp, 0);
   if (*pTemp == '.'
    || *pTemp == 'e' || *pTemp == 'E'
#if(0)
    || *pTemp == 'f' || *pTemp == 'F'
#endif
    )
   {
    isFloat = TRUE;
   }
   else
   {
    pToken->tokenType = OperandInteger;
    pToken->intValue = intValue;
    pMovBuf = pTemp;
   }/*is float*/
  }/*local variable*/

  if (FALSE != isFloat)
  {
   pToken->floatValue = strtod(pMovBuf, &pMovBuf);
   pToken->tokenType = OperandFloat;
#if(0)
   if ('f' == *pMovBuf || 'F' == *pMovBuf)
    pMovBuf++;
#endif
  }/*FALSE == isFloat*/

  goto Flag_End_GetToken;
 }/* operand */


 {
  /*Token is an operator*/  
  char symbol;
  symbol = *pMovBuf;
  pToken->tokenType = Operator;

  switch (symbol)
  {
  case '+':
   pToken->operatorType = OP_PLUS;
   break;
  case '-':
   pToken->operatorType = OP_MINUS;
   break;
  case '*':
   pToken->operatorType = OP_MULTIPLY;
   break;
  case '/':
   pToken->operatorType = OP_DIVIDE;
   break;

  case '^':
   pToken->operatorType = OP_POWER;
   break;
  case '%':
   pToken->operatorType = OP_MOD;
   break;

  case '(':
   pToken->operatorType = OP_LPAREN;
   break;

  case ')':
   pToken->operatorType = OP_RPAREN;
   break;

  default:
   pToken->operatorType = OP_UNKOWN;
   pToken->unknownSymbol = symbol;
   break;
  }/*switch*/

  pToken->tokenType = Operator;
  pMovBuf++;
 }/*operator */

Flag_End_GetToken:

 tokenLen = (int)(pMovBuf - pStr);
 *pCostedStrLen = tokenLen;

 return tokenLen;
}/*GetToken*/


int GetTokens(char *pStr, int strLen, struct TokenProperty *pTokenArray)
{
 int costedSize;
 int k;
 char *pMovBuf; 

 pMovBuf = pStr; 

 k = 0;

 while (0 < strLen)
 {
  GetNextToken(pMovBuf, strLen, &pTokenArray[k], &costedSize);

  pMovBuf += costedSize;
  strLen -= costedSize;
  k++;  
 }/*while 0 < strLen*/


 {/*check if there is unknownSymbol*/
  int i;    
  for (i = 0; i < k; i++)
  {
   if (Operator == pTokenArray[i].tokenType &&
    OP_UNKOWN == pTokenArray[i].operatorType)
   {
    printf("Error : character %c unknown\n",
     pTokenArray[i].unknownSymbol);

    return -1;
   }/*if */

  }/*for i*/
  
 }/*local variable*/

#ifndef _DEBUG
 /*check if there is grammatical error*/
 {
  int i;
  struct TokenProperty previousToken;

  memcpy(&previousToken, &pTokenArray[0],
   sizeof(struct TokenProperty));

  for (i = 1; i < k; i++)
  {   
   switch (pTokenArray[i].tokenType)
   {
   case Operator:
    if (Operator == previousToken.tokenType
     && OP_LPAREN != previousToken.operatorType
     && OP_RPAREN != previousToken.operatorType)
    {
     printf("error : two operator have been"
      " put together !\n");
     return -2;
    }
    break;
   case OperandFloat:
   case OperandInteger:
    if (OperandFloat == previousToken.tokenType
     || OperandInteger == previousToken.tokenType)
    {
     printf("error : two operend have been" 
      " put together !\n");
     return -3;
    }
    break;
   }/*switch*/

   memcpy(&previousToken, &pTokenArray[i],
    sizeof(struct TokenProperty));
  }/*for i*/
 }/*local variable*/ 

#endif /*_DEBUG*/

 return k;
}/*GetTokens*/


int InfixArrayToPostfixStack(int nInfixToken, struct TokenProperty *pTokens)
{
 struct TokenProperty *pTokenInfixArray;
 struct TokenProperty *pTokenPostfixStack;

 struct TokenProperty *pCurrentToken;

 unsigned char precedence[MAX_STR_LEN];
 int i;
 int nPostfixToken;
 int operatorStackTop;

 struct TokenProperty *pOperatorTokenStack;
 
 
 pTokenInfixArray = pTokens;

 if (0 >= nInfixToken)
  return -1;

 { /*initialize the precedence array*/

  memset(&precedence[0], 0, MAX_STR_LEN);
  precedence[OP_PLUS] = 1; precedence[OP_MINUS] = 1;
  precedence[OP_MULTIPLY] = 2; precedence[OP_DIVIDE] = 2;
  precedence[OP_POWER] = 3; precedence[OP_DIVIDE] = 2;

  precedence[OP_LPAREN] = 255; precedence[OP_RPAREN] = 254;
  precedence[OP_UNKOWN] = 0;
 }/*local block*/

 pOperatorTokenStack =
  (struct TokenProperty*)malloc((nInfixToken)*sizeof(struct TokenProperty));
 memset(pOperatorTokenStack, 0, (nInfixToken)*sizeof(struct TokenProperty));

 pTokenPostfixStack =
  (struct TokenProperty*)malloc(nInfixToken*sizeof(struct TokenProperty)); 
 memset(pTokenPostfixStack, 0, nInfixToken*sizeof(struct TokenProperty));

 pCurrentToken = &pTokenInfixArray[0];
 
 operatorStackTop = -1;
 nPostfixToken = 0;

 for (i = 0; i < nInfixToken; i++)
 {
  enum TokenType tokenType;
  tokenType = pCurrentToken->tokenType;

  switch (tokenType)
  {  
  case OperandInteger:
  case OperandFloat:
   memcpy(&pTokenPostfixStack[nPostfixToken],
    pCurrentToken, sizeof(struct TokenProperty));
   nPostfixToken += 1;
   break;
  case Operator:
   switch (pCurrentToken->operatorType)
   {
   case OP_UNKOWN:
    printf("Unknown operator %c\n", pCurrentToken->unknownSymbol);
    return -2;

   case OP_PLUS:
   case OP_MINUS:
   case OP_MULTIPLY:
   case OP_DIVIDE:
   case OP_POWER:
   case OP_MOD:
    if (0 <= operatorStackTop)
    {
     
     /*if there is no parenthesis to force current operator 
      subduing previous operator*/
     if (OP_LPAREN !=
      pOperatorTokenStack[operatorStackTop].operatorType)
     {
      enum OperatorType operatorStackTopType;
      operatorStackTopType 
       = pOperatorTokenStack[operatorStackTop].operatorType;

      /*if previous operator subdues current operator,
      ouput the operatorStackTop one to postfix stack */

      if (precedence[pCurrentToken->operatorType] <
       precedence[operatorStackTopType])
      {

       memcpy(&pTokenPostfixStack[nPostfixToken],
        &pOperatorTokenStack[operatorStackTop],
        sizeof(struct TokenProperty));
       nPostfixToken += 1;
       operatorStackTop -= 1;
      }/*if */
     }/*keep ( in the stack */
    }/*stack is not empty*/

    operatorStackTop += 1;
    memcpy(&pOperatorTokenStack[operatorStackTop], pCurrentToken,
     sizeof(struct TokenProperty));
    break;

   case OP_LPAREN:
    operatorStackTop += 1;
    memcpy(&pOperatorTokenStack[operatorStackTop], pCurrentToken,
     sizeof(struct TokenProperty));
    break;

   case OP_RPAREN:
    while ( OP_LPAREN != 
     pOperatorTokenStack[operatorStackTop].operatorType)
    {
     if (0 > operatorStackTop)
     {
      printf("error : ( could not be found! \n");
      return -3;
     }/*not balance*/

     memcpy(&pTokenPostfixStack[nPostfixToken],
      &pOperatorTokenStack[operatorStackTop],
      sizeof(struct TokenProperty));

     nPostfixToken += 1;
     operatorStackTop -= 1;
    }/*while parenthesis is balance*/

    operatorStackTop -= 1;
    break;

   default:
    break;
   }/*switch*/

   break;
  case Unknown:
   //printf("unknow token type %d");
   return -2;
  }/*switch*/

  pCurrentToken++;
 }/*while ExpressionEnd != pCurrentToken->tokenType*/
 

 /*inverse output to postfix stack*/
 while (0 <= operatorStackTop)
 {
  
  if (OP_LPAREN == pOperatorTokenStack[operatorStackTop].operatorType)
  {
   printf("error : ) could not be found! \n");
   return -3;
  }/*not balance*/
  
  memcpy(&pTokenPostfixStack[nPostfixToken], 
   &pOperatorTokenStack[operatorStackTop], sizeof(struct TokenProperty)); 
  nPostfixToken += 1;
  operatorStackTop -= 1;
 }/*while*/
 
 memcpy(pTokens, pTokenPostfixStack, nPostfixToken*sizeof(struct TokenProperty));

 free(pTokenPostfixStack); pTokenPostfixStack = NULL;

 return nPostfixToken;
}/*TokenArrayInfixToPostfix*/


long long ipow(int base, int exp)
{
 long long result = 1;

 while (exp)
 {
  if (exp & 1)
   result *= base;
  base *= base;
  exp >>= 1;
 }

 return result;
}/*ipow*/


union evaluateType
{
 long long integerType;
 double floatType;
};


int EvaluatePostfixStack(int nPostfixToken, struct TokenProperty *pTokenPostfixStack,
 int *pIsFloat, union evaluateType *pResult)
{
 int i;
 int isThereFloat;
 isThereFloat = FALSE;
 union evaluateType *pOperandStack;
 int top;

#ifdef _FORCE_FLOATING_ARITHMETIC
 isThereFloat = TRUE;
#else
 for (i = 0; i < nPostfixToken; i++)
 {
  if (OperandFloat == pTokenPostfixArray[i].tokenType)
  {
   isThereFloat = TRUE;
   break;
  }/*if*/  
 }/*for i*/
#endif

 if (FALSE != isThereFloat)
 {
  for (i = 0; i < nPostfixToken; i++)
  {
   if (OperandInteger == pTokenPostfixStack[i].tokenType)
   {
    pTokenPostfixStack[i].tokenType = OperandFloat;
    pTokenPostfixStack[i].floatValue
     = (double)pTokenPostfixStack[i].intValue;
   }/*if */
  }/*for i*/
 }/*if FALSE != isThereFloat*/


 pOperandStack = 
  (union evaluateType*)malloc(nPostfixToken*sizeof(union evaluateType));

 top = -1;
 
 for (i = 0; i < nPostfixToken; i++)
 {
  switch (pTokenPostfixStack[i].tokenType)
  {
  case OperandFloat:
   top += 1;
   pOperandStack[top].floatType
    = pTokenPostfixStack[i].floatValue;
   break;

  case OperandInteger:
   top += 1;
   pOperandStack[top].integerType
    = pTokenPostfixStack[i].intValue;
   break;

  case Operator:
   {
    union evaluateType a, b, c;

    if (OP_RPAREN == pTokenPostfixStack[i].operatorType
     || OP_LPAREN == pTokenPostfixStack[i].operatorType)
    {
     break;
    }/*ingore parenthesis*/

    if (0 > top)
    {
     printf("error,  deficiency of operand!");
     return -4;
    }

    if (FALSE == isThereFloat)
     b.integerType = pOperandStack[top].integerType;
    else
     b.floatType = pOperandStack[top].floatType;

    top -= 1;


    if (0 > top)
    {
     
     printf("error, lacking operand !");
     return -3;
    }
    if (FALSE == isThereFloat)
     a.integerType = pOperandStack[top].integerType;
    else
     a.floatType = pOperandStack[top].floatType;

    top -= 1;

    switch (pTokenPostfixStack[i].operatorType)
    {
    case OP_UNKOWN:
     printf("Unknown operator %c\n", 
      pTokenPostfixStack[i].unknownSymbol);
     return -2;
    
    case OP_PLUS:
     if (FALSE == isThereFloat)
      c.integerType = a.integerType + b.integerType;
     else
      c.floatType = a.floatType + b.floatType;
     break;

    case OP_MINUS:
     if (FALSE == isThereFloat)
      c.integerType = a.integerType - b.integerType;
     else
      c.floatType = a.floatType - b.floatType;
     break;

    case OP_MULTIPLY:
     if (FALSE == isThereFloat)
      c.integerType = a.integerType * b.integerType;
     else
      c.floatType = a.floatType * b.floatType;
     break;

    case OP_DIVIDE:

     if (FALSE == isThereFloat)
      c.integerType = a.integerType / b.integerType;
     else
      c.floatType = a.floatType / b.floatType;
     break;

    case OP_POWER:
     if (FALSE == isThereFloat)
      c.integerType 
      = ipow((int)a.integerType, (int)b.integerType);
     else
      c.floatType = pow(a.floatType, b.floatType);
     break;

    case OP_MOD:
     if (FALSE == isThereFloat)
      c.integerType = a.integerType % b.integerType;
     else
      c.floatType = fmod(a.floatType, b.floatType);
     break;
    
    default:
     break;
    }/*switch (pTokenPostfixArray[i].operatorType)*/

    top += 1;
    pOperandStack[top] = c;
   }/*Operator*/   
   break;

  case Unknown:
   printf("Unknown operator %c\n", pTokenPostfixStack[i].unknownSymbol);
   return -1;
   break;

  case ExpressionEnd:   
   break;
  default:
   break;
  }/*switch*/
    
 }/*for i */
 
 *pIsFloat = isThereFloat;
 *pResult = pOperandStack[0];

 free(pOperandStack); pOperandStack = NULL;

 if (0 != top)
 {
  printf("error, lacking operator between two operands  !");
  return -5;
 }/*if not only top exists*/ 

 return 0;
}/*EvaluatePostfix*/

#define CONFIRMED_SIZE      (4) // for Expression End


int main(int argc, char *argv)
{
 char inputStr[MAX_STR_LEN];
 int strLen;

 struct TokenProperty *pTokens;
 int nToken;

 int isFloat;
 union evaluateType result;

 memset(&inputStr[0], 0, MAX_STR_LEN);

 printf("input your expression:\n");

 fgets(&inputStr[0], MAX_STR_LEN, stdin);
 strLen = (int)strlen(&inputStr[0]);

 nToken = GetTokenNumber(&inputStr[0], strLen);

 pTokens =
  (struct TokenProperty*)malloc(
   (nToken + CONFIRMED_SIZE)*sizeof(struct TokenProperty));

 memset(pTokens, 0, (nToken + CONFIRMED_SIZE)*sizeof(struct TokenProperty));

 nToken = GetTokens(&inputStr[0], strLen, pTokens);
 if (0 > nToken)
  return -1;

 nToken = InfixArrayToPostfixStack(nToken, pTokens);
 if (0 > nToken)
  return -2;

 PrintTokenProperty(nToken, pTokens);

 if (0 > EvaluatePostfixStack(nToken, pTokens, &isFloat, &result))
   return -3;

 free(pTokens); pTokens = NULL;
 
 if (FALSE == isFloat)
  printf(" = %lld\n", result.integerType);
 else
  printf(" = %f\n", result.floatType);

 return 0;
}/*main*/

Run the code:

input your expression:
(1 +2)^2.5/(2*0.2)
 = 38.971143

Explaination:

The code is straightforward, the postfix stack has been adopted in here:

the concept of postfix stack is :


零.  create a temporary stack to store opeators.

example :

a + b + c :
 

a
b
c

+
+

The combination of the two stack be :

a
b
c
+
+

一. The operator is put more late, the precedence would be more high in nature. It is the general rule to make the postfix stack.


example :

 a + b - c

a
b
c
-
+

二. While precedence  of previous operator is higher than current's, put previous operator into postfix stack.

example :

 a  * b  + c

a
b
*
c
+

Explanation : the precedence  of multiplication is higher that addition. Once while the addition would be put into opation stack, I should move the multiplication (the previous one in the operator stack ) into the postfix stack first.




三. While there is a right parenthesis, move all the opeators from the opeartor stack into the postfix stack until encountering a left parenthesis:

example :

(a^b * c) - d

a
b
^
c
*
d
-

Explanation : The power opeator would be put in the postfix stack in first by the rule 二, and the multiplication would be store in the operator stack for further processing; Once the rght  parenthesis has been enoutered, the multiplication would be move into the postfix stack from the operator stack.


Above is my  cognition of postfix stack algorithm, I hope it is useful for you.