字尾表達式的原理

完整代碼

/*
 * 程式名：seqstack3.c，此程式示範用順序棧實作中綴表達式轉字尾表達式。
 * 作者：C語言技術網(www.freecplus.net) 日期：20201230
*/
#include <stdio.h>
#include <string.h>

#define MAXSIZE 100      // 順序棧的最大長度。   // xxxxx

typedef char ElemType;    // 自定義順序棧的資料元素為字元。 // xxxx

typedef struct
{
  ElemType data[MAXSIZE];   // 用數組存儲順序棧中的元素。
  int top;                  // 棧頂指針，從0到MAXSIZE-1，-1表示空棧。
                            // 也可以從1到MAXSIZE，0表示空棧。
}SeqStack,*PSeqStack;

// 順序棧SS的初始化操作。
void InitStack(PSeqStack SS);                     

// 銷毀順序棧SS。
void DestroyStack(PSeqStack SS);

// 元素入棧，傳回值：0-失敗；1-成功。
int Push(PSeqStack SS, ElemType *ee);

// 元素出棧，傳回值：0-失敗；1-成功。
int Pop(PSeqStack SS, ElemType *ee);

// 求順序棧的長度，傳回值：棧SS中元素的個數。
int Length(PSeqStack SS);                   

// 清空順序棧。
void Clear(PSeqStack SS);                    

// 判斷順序棧是否為空，傳回值：1-空，0-非空或失敗。
int IsEmpty(PSeqStack SS);                    

// 判斷順序棧是否已滿，傳回值：1-已滿，0-未滿或失敗。
int IsFull(PSeqStack SS);

// 列印順序棧中全部的元素。
void PrintStack(PSeqStack SS);                    

// 擷取棧頂元素，傳回值：0-失敗；1-成功。
// 隻檢視棧頂元素的值，元素不出棧。
int GetTop(PSeqStack SS, ElemType *ee);

// 把中綴表達式str1轉換為字尾表達式str2。
int torpolish(char *str1,char *str2);

int main(int argc,char *argv[])
{
  char str1[101],str2[101];  
  memset(str1,0,sizeof(str1));
  memset(str2,0,sizeof(str2));

  printf("請輸入待轉換的表達式：");
  fgets(str1,100,stdin);     // 不建議用gets函數，gets函數編譯時可能會出現警号。
  str1[strlen(str1)-1]=0;    // 删除str1最後的換行。
  printf("輸入轉換的表達式=%s=\n",str1);

  // 把中綴表達式str1轉換為字尾表達式str2。
  if (torpolish(str1,str2) == 0) { printf("轉換失敗。\n"); return -1; }

  printf("轉換成功=%s=。\n",str2);

  return 1;
}

// 把中綴表達式str1轉換為字尾表達式str2。
int torpolish(char *str1,char *str2)
{
  SeqStack SS;     // 建立順序棧。
  InitStack(&SS);  // 初始化順序棧。

  ElemType ee;     // 建立一個資料元素。

  int ipos1=0,len=strlen(str1),ipos2=0;

  // 從左到右掃描中綴表達式。
  for (ipos1=0;ipos1<len;ipos1++)
  {
    // 數字和字母直接追加到字尾表達式後面。
    if ( ( (str1[ipos1]>='0') && (str1[ipos1]<='9') ) ||
         ( (str1[ipos1]>='a') && (str1[ipos1]<='z') ) ||
         ( (str1[ipos1]>='A') && (str1[ipos1]<='Z') ) )
    {
      str2[ipos2]=str1[ipos1]; ipos2++; continue;
    }

    // 左括号'('直接入棧。
    if (str1[ipos1]=='(')  { Push(&SS,&str1[ipos1]); continue; }

    // 如果是右括号')'，依次彈出棧中的運算符并追加到字尾表達式中，直到出現左括号'('。
    if (str1[ipos1]==')')  
    {
      while (1)
      {
        // 一定要判斷出棧結果，如果棧中沒有元素，轉換失敗（因為沒找到左括号'('）。
        if ( Pop(&SS,&ee) != 1) return 0;  
        if ( ee == '(') break;
        str2[ipos2]=ee; ipos2++;
      }

      continue;
    }

    // 如果是算術運算符'+'、'-'、'*'、'/'。
    if ( (str1[ipos1]=='+') || (str1[ipos1]=='-') || (str1[ipos1]=='*') || (str1[ipos1]=='/') )
    {
      while (1)
      {
        // 擷取棧中運算符，如果棧為空，目前運算符直接入棧。
        if (GetTop(&SS,&ee) != 1) break;

        if ( ee=='(' ) break;  // 如果遇到左括号，停止判斷，目前運算符将入棧。

        int pri1;   // 目前運算符的優先級。
        int pri2;   // 棧中運算符的優先級。

        if ( (str1[ipos1]=='+') || (str1[ipos1]=='-') ) pri1=1;
        if ( (str1[ipos1]=='*') || (str1[ipos1]=='/') ) pri1=2;
        if ( (ee=='+') || (ee=='-') ) pri2=1;
        if ( (ee=='*') || (ee=='/') ) pri2=2;

        // 如果目前運算符的優先級 高于 棧中運算符的優先級，停止判斷，目前運算符将入棧。
        if (pri1>pri2) break;  
        
        // 把棧中優先級 高于等于 目前運算符的元素依次彈出，追加到字尾表達式後面。
        Pop(&SS,&ee); str2[ipos2]=ee; ipos2++; continue;
      }

      // 目前運算符入棧。
      Push(&SS,&str1[ipos1]); 

      continue;
    }
  }

  // 彈出棧中其它的運算符，追加到字尾表達式後面。
  while (1)
  {
    if (Pop(&SS,&ee)!=1) break;

    str2[ipos2]=ee; ipos2++;
  }

  return 1;
}

// 初始化順序棧
void InitStack(PSeqStack SS)
{
  Clear(SS); // 清空順序棧。
}

// 清空順序棧。
void Clear(PSeqStack SS)
{
  if (SS == NULL) return; // 檢查空指針。

  SS->top=-1;  // 棧頂指針置為-1。
  memset(SS->data,0,sizeof(ElemType)*MAXSIZE);  // 數組元素清零。
}

// 求順序棧的長度，傳回值：棧SS中元素的個數。
int Length(PSeqStack SS)
{
  if (SS == NULL) return 0; // 檢查空指針。

  return SS->top+1;
}

// 銷毀順序棧SS。
void DestroyStack(PSeqStack SS)
{
  // 靜态順序棧無需釋放記憶體，不需要銷毀操作。

  Clear(SS); // 清空順序棧。

  return;
}

// 判斷順序棧是否為空，傳回值：1-空，0-非空或失敗。
int IsEmpty(PSeqStack SS)
{
  if (SS == NULL) return 0;  // 檢查空指針。

  if (SS->top == -1) return 1;

  return 0;
}

// 判斷順序棧是否已滿，傳回值：1-已滿，0-未滿或失敗。
int IsFull(PSeqStack SS)
{
  if (SS == NULL) return 0;  // 檢查空指針。

  if (SS->top >= MAXSIZE-1) return 1;

  return 0;
}

// 元素入棧，傳回值：0-失敗；1-成功。
int Push(PSeqStack SS, ElemType *ee)
{
  if ( (SS == NULL) || (ee == NULL) ) return 0;  // 檢查空指針。

  if (IsFull(SS) == 1)
  {
    printf("順序棧已滿，不能插入。\n"); return 0;
  }

  SS->top++;  // 棧指針先加1。

  memcpy(&SS->data[SS->top],ee,sizeof(ElemType));  // 用數組的下标通路。
  // memcpy(SS->data+SS->top,ee,sizeof(ElemType));    // 采用指針運算也可以。

  return 1;
}

// 列印順序棧中全部的元素。
void PrintStack(PSeqStack SS)
{
  if (SS == NULL) return;  // 檢查空指針。

  if (SS->top == -1) { printf("棧為空。\n"); return; }

  int kk;
  for (kk = 0; kk <= SS->top; kk++)
  {
    printf("SS[%d],value=%c\n",kk,SS->data[kk]);     // 用數組的下标通路。 xxx
    // printf("SS[%d],value=%d\n",kk,*(SS->data+kk));   // 采用指針運算也可以。
  }
}

// 元素出棧，傳回值：0-失敗；1-成功。
int Pop(PSeqStack SS, ElemType *ee)
{
  if ( (SS == NULL) || (ee == NULL) ) return 0;  // 檢查空指針。

  if (SS->top == -1) { printf("棧為空。\n"); return 0; }

  memcpy(ee,&SS->data[SS->top],sizeof(ElemType));  // 用數組的下标通路。
  // memcpy(ee,SS->data+SS->top,sizeof(ElemType));    // 采用指針運算也可以。

  SS->top--;  // 棧指針減1。

  return 1;
}

// 擷取棧頂元素，傳回值：0-失敗；1-成功。
// 隻檢視棧頂元素的值，元素不出棧。
int GetTop(PSeqStack SS, ElemType *ee)
{
  if ( (SS == NULL) || (ee == NULL) ) return 0;  // 檢查空指針。

  if (IsEmpty(SS) == 1) { printf("棧為空。\n"); return 0; }

  memcpy(ee,&SS->data[SS->top],sizeof(ElemType));  // 用數組的下标通路。
  // memcpy(ee,SS->data+SS->top,sizeof(ElemType));    // 采用指針運算也可以。

  return 1;
}