C語言資料結構與演算法 - 表示式解析

像2*(3*4)這樣的普通算術表示式，人腦更容易解析，但對於演算法來說，解析這樣的表示式相當困難。為了簡化這個難度，可以使用兩步法來解析算術表示式。

• 將給定的算術表示式轉換為字尾表示式。

• 計算字尾表示式。

中綴表示式

普通的算術表示式遵循中綴表示法，其中運算子位於運算元之間。例如，A+B中，A是第一個運算元，B是第二個運算元，+是作用於這兩個運算元的運算子。

字尾表示式

字尾表示式與普通的算術表示式或中綴表示式不同，運算子位於運算元之後。例如，考慮以下例子。

中綴表示式轉字尾表示式

在研究中綴表示式到字尾表示式的轉換方法之前，我們需要考慮中綴表示式計算的以下基礎知識。

• 中綴表示式的計算從左到右開始。

• 記住優先順序，例如*的優先順序高於+。例如

  • 2+3*4 = 2+12.

  • 2+3*4 = 14.

• 使用括號覆蓋優先順序，例如

  • (2+3)*4 = 5*4.

  • (2+3)*4= 20.

現在讓我們手動將簡單的中綴表示式A+B*C轉換為字尾表示式。

現在讓我們使用棧將上述中綴表示式A+B*C轉換為字尾表示式。

現在讓我們看另一個例子，使用棧將中綴表示式A*(B+C)轉換為字尾表示式。

示例

現在我們將演示使用棧將中綴表示式轉換為字尾表示式，然後計算字尾表示式的過程。

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

//char stack
char stack[25]; 
int top=-1; 

void push(char item) { 
   stack[++top]=item; 
}
char pop() { 
   return stack[top--]; 
}

//returns precedence of operators
int precedence(char symbol) { 
   switch(symbol) { 
      case '+': 
      case '-':
         return 2; 
         break; 
      case '*': 
      case '/':
         return 3; 
         break; 
      case '^': 
         return 4; 
         break; 
      case '(': 
      case ')': 
      case '#':
         return 1; 
         break; 
   }
}

//check whether the symbol is operator?
int isOperator(char symbol) { 
   switch(symbol){ 
      case '+': 
      case '-': 
      case '*': 
      case '/': 
      case '^': 
      case '(': 
      case ')':
         return 1; 
      break; 
         default:
         return 0; 
   } 
}
//converts infix expression to postfix
void convert(char infix[],char postfix[]){ 
   int i,symbol,j=0; 
   stack[++top]='#'; 
   for(i=0;i<strlen(infix);i++){ 
      symbol=infix[i]; 
      if(isOperator(symbol)==0){ 
         postfix[j]=symbol; 
         j++; 
      } else {
         if(symbol=='('){			
            push(symbol); 
         } else { 
            if(symbol==')'){ 
               while(stack[top]!='('){ 
                  postfix[j]=pop(); 
                  j++; 
               } 
               pop();//pop out (. 
            } else { 
               if(precedence(symbol)>precedence(stack[top])) {
                  push(symbol); 
               } else { 
                  while(precedence(symbol)<=precedence(stack[top])) { 
                     postfix[j]=pop(); 
                     j++; 
                  } 
                  push(symbol); 
               }
            }
         }
      }
   }
   while(stack[top]!='#') {
      postfix[j]=pop(); 
      j++; 
   }
   postfix[j]='\0';//null terminate string. 
} 
//int stack
int stack_int[25]; 
int top_int=-1; 

void push_int(int item) { 
   stack_int[++top_int]=item; 
} 

char pop_int() { 
   return stack_int[top_int--]; 
} 
//evaluates postfix expression
int evaluate(char *postfix){
   char ch;
   int i=0,operand1,operand2;

   while( (ch=postfix[i++]) != '\0') {
      if(isdigit(ch)){ 
	     push_int(ch-'0'); // Push the operand 
      } else {
         //Operator,pop two  operands 
         operand2=pop_int();
         operand1=pop_int();
         switch(ch) {
            case '+':
               push_int(operand1+operand2);
               break;
            case '-':
               push_int(operand1-operand2);
               break;
            case '*':
               push_int(operand1*operand2);
               break;
            case '/':
               push_int(operand1/operand2);
               break;
         }
      }
   }
   return stack_int[top_int];
}
void main() {
   char infix[25] = "1*(2+3)",postfix[25]; 
   convert(infix,postfix); 
   printf("Infix expression is: %s\n" , infix);
   printf("Postfix expression is: %s\n" , postfix);
   printf("Evaluated expression is: %d\n" , evaluate(postfix));
} 

輸出

如果我們編譯並執行上述程式，它將產生以下輸出：

Infix expression is: 1*(2+3)
Postfix expression is: 123+*
Result is: 5