C語言實作表達式求值，支援+、-、*、/四則運算，并且支援多級括号，自定義了棧的操作。

以下是代碼的實作使用gcc已經成功運作了，下面是效果圖           

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

#define OPT_ADD 43 /* + */
#define OPT_SUB 45 /* - */
#define OPT_MUL 42 /* * */
#define OPT_DIV 47 /* / */
#define L_BRACK 40 /* ( */

typedef struct _stack
{
  int  data; /* 棧内元素 */
  struct _stack *next;
}Stack; /* 定義棧結構! */

/**
* 壓棧
* 頭插法,将資料壓到頭結點
**/
int push_stack(Stack **stack, int data)
{
  Stack *p = (Stack*)malloc(sizeof(Stack));
  if (NULL == p)
    exit(-1); /* 申請記憶體都不行,挂了 */
  p->data = data;
  p->next = *stack;
  *stack = p;
  return 0;
}

/**
* 彈棧
* 頭指針就是棧頂
**/
int pop_stack(Stack **stack)
{
  Stack *p = *stack;  /* 緩存頭指針 */
  if (NULL == p)
    return -1;        /* 棧已經空了 */
  int data = p->data; /* 緩存棧頂資料 */
  *stack  = p->next;  /* 棧頂移動  */
  free(p);            /* 釋放記憶體  */
  return data;
}

/**
* 擷取棧頂元素
**/
int get_top_stack(Stack *stack)
{
  return stack->data; /* 頭指針就是棧頂 */
}

/**
* 判斷棧空
**/
int stack_is_empty(Stack *stack)
{
  return NULL == stack ? 1 : 0;
}

/**
* 棧内元素個數
**/
int count_stack(Stack *stack)
{
  int cnt = 0;
  while (NULL != stack)
  {
    cnt++;
    stack = stack->next;
  }
  return cnt;
}

/**
* 銷毀棧
**/
void destroy_stack(Stack **stack)
{
  Stack *p = *stack, *q;
  while (NULL != p)
  {
    q = p->next;
    free(p);
    p = q;
  }
  *stack = NULL;
}

/**
* 顯示所有棧元素
**/
void show_stack(const char *name, Stack *stack)
{
  printf("[%s: ", name);
  while (NULL != stack)
  {
    printf("%d,", stack->data);
    stack = stack->next; /* 從棧頂依次列印 */
  }
  printf("]\n");
}

/**
* 計算a和b在mode符号的運算結果
**/
int cal(int a,int b,int mode)
{
  int re = -1;
  switch(mode)
  {
  case OPT_ADD: re = a + b; break;
  case OPT_SUB: re = a - b; break;
  case OPT_MUL: re = a * b; break;
  case OPT_DIV: re = a / b; break;
  default: break;
  }
  return re;
}

/**
* 符号優先級判斷
* 傳回： 1(opt1>opt2) -1(opt1<opt2) 0(opt1=opt2)
* 注意符号的ASSIC碼：43(+) 45(-) 42(*) 47(/)
**/
int opt_max(int opt1,int opt2)
{
  if(OPT_MUL == opt1 || OPT_DIV == opt1)
  {
    if(OPT_ADD == opt2 || OPT_SUB == opt2)
    {
      return 1;
    }
  }
  else
  {
    if(OPT_MUL == opt2 || OPT_DIV == opt2)
    {
      return -1;
    }
  }
  return 0;
}

/**
* 計算表達式
**/
int calculate(const char *expr)
{
  int num1, num2, opt1, opt2;
  Stack *num = NULL;
  Stack *opt = NULL;
  while ('\0' != *expr)
  {
    if ('(' == *expr)
    { /* 左括号 */
      push_stack(&opt, (int)*expr++); /* 壓符号棧 */
    }
    else if (')' == *expr)
    { /* 右括号 */
      expr++; /* 指針加1 */
      while (1)
      {
        if (L_BRACK == get_top_stack(opt))
        {
          pop_stack(&opt);
          break; /* 如果目前棧頂是(則弾棧退出 */
        }
        else
        { /* 否則弾兩個數字，一個符号進行運算 */
          num2 = pop_stack(&num);
          num1 = pop_stack(&num);
          opt2 = pop_stack(&opt);
          push_stack(&num, cal(num1, num2, opt2));
        }
      }
    }
    else if ('9' >= *expr && '0' <= *expr)
    { /* 數字 */
      sscanf(expr, "%d", &num1);
      push_stack(&num, num1);
      num2 = 0;     /* 記錄num1的長度 */
      while (0 != num1) {num2++; num1 /= 10;}
      expr += num2; /* 指針移動指定長度 */
    }
    else if (*expr == OPT_ADD || *expr == OPT_SUB || *expr == OPT_MUL || *expr == OPT_DIV)
    { /* 加減乘除,這4個符号 */
      opt1 = (int)*expr++;
      while (1)
      {
        if (stack_is_empty(opt) || L_BRACK == get_top_stack(opt))
        {
          push_stack(&opt, opt1);
          break;
        }
        else
        {
          opt2 = get_top_stack(opt);
          if (0 < opt_max(opt1, opt2))
          { /* 目前擷取的符号優先級大于棧頂符号 */
            push_stack(&opt, opt1);
            break;
          }
          else
          { /* 棧頂優先級高或者平級 */
            num2 = pop_stack(&num);
            num1 = pop_stack(&num);
            opt2 = pop_stack(&opt);
            push_stack(&num, cal(num1, num2, opt2));
          }
        }
      }
    } else {
      printf("expression error\n");
      num1 = -1; /* 這種是表達式錯誤 */
      goto MUST_END;
    }
  }

  num1 = count_stack(num);
  num2 = count_stack(opt);
  if (num1 == 3 && num2 == 2) {
    num2 = pop_stack(&num);
    num1 = pop_stack(&num);
    opt2 = pop_stack(&opt); /* 剩餘3個數字和2個操作符,需要多計算一次 */
    push_stack(&num, cal(num1, num2, opt2));
  } else if (num1 == 2 && num2 == 1) {
    /* 剩餘2個數字和1個操作符,最後隻計算1次 */
  } else {
    printf("expression error\n");
    num1 = -1; /* 這種是表達式錯誤 */
    goto MUST_END;
  }
  num2 = pop_stack(&num);
  num1 = pop_stack(&num);
  opt2 = pop_stack(&opt);
  num1 = cal(num1, num2, opt2);

MUST_END:
  destroy_stack(&num); /* 銷毀num棧 */
  destroy_stack(&opt); /* 銷毀opt棧 */
  return num1;
}

/**
* 主程式
* 放在最下面,避免重複聲明函數
**/
int main(int argc, char *argv[])
{
  if (argc == 2) {
    printf("%s=%d\n", argv[1], calculate(argv[1]));
  } else {
    printf("usage:%s expression\n", argv[0]);
  }
  return 0;
}
           

至于原理嘛棧的操作我就不多叙述了。主要講講算法的事情，首先計算函數開始的時候就建立了數字棧和符号棧。處理的時候把所有字元串裡取出來的東西都在棧裡用整形儲存，這樣可以統一數字棧和符号棧是同種結構。當周遊字元串時遇到數字字元就把目前開始的數字取出來壓數字棧，當遇到左括号是總是壓符号棧不管連續多少個左括号，當遇到右括号時就從數字棧和符号棧中取值計算并從新壓棧，直到遇到左括号，期間還要比較運算符的優先級等。當遇到字元串結束時還沒有計算完成，此時數字棧和字元棧内都有值。如果數字棧為3個，符号棧為2個那麼要計算兩次，如果數字棧為2個，符号棧為1個計算一次。最終得出結果。我寫這個程式時思路還是清晰的，就是不知道有沒有小問題，希望能給大家一些啟發。測試出問題也希望大家給我說，大家一起進步嘛。

作者：janbar

出處：https://www.cnblogs.com/janbar

本文版權歸作者和部落格園所有，歡迎轉載，轉載請标明出處。喜歡我的文章請 [關注我] 吧。

如果您覺得本篇博文對您有所收獲，可點選 [推薦] 并 [收藏] ，或到右側 [打賞] 裡請我喝杯咖啡，非常感謝。