1. WIKI教程
2. 数据结构和算法
3. 点击这里

点击这里

Infix符号对于人类来说更容易阅读和理解，而对于像计算机这样的电子机器，postfix是解析的最佳表达形式。 我们将在这里看到一个程序，用于将中infix符号转换和评估为postfix表示法 -

例子 (Example)

#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));
} 

如果我们编译并运行上面的程序，它将产生以下结果 -

输出 (Output)

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