HTML CSS JAVASCRIPT PYTHON PYTHON2 JAVA C C++ C# SQL Excel Linux AI BOOTSTRAP PHP 教程库 参考手册 技术文章 测验 练习 HOWTO FAQ
❮ 上一节 下一节 ❯

使用 C 的 DSA - 解析表达式

像 2*(3*4) 这样的普通算术表达式更容易被人脑解析，但对于算法来说，解析这样的表达式会相当困难。为了缓解这种困难，可以使用两步方法通过算法解析算术表达式。

  • 将提供的算术表达式转换为后缀表示法。

  • 评估后缀表示法。

中缀表示法

普通算术表达式遵循中缀表示法，其中运算符位于操作数之间。例如 A+B 此处 A 是第一个操作数，B 是第二个操作数，+ 是作用于两个操作数的运算符。

后缀表示法

后缀表示法与普通算术表达式或中缀表示法不同，因为运算符位于操作数之后。例如，请考虑以下示例。

Sr. No. 中缀表示法 后缀表示法
1 A+B AB+
2 (A+B)*C AB+C*
3 A*(B+C) ABC+*
4 A/B+C/D AB/CD/+
5 (A+B)*(C+D) AB+CD+*
6 ((A+B)*C)-D AB+C*D-

中缀到后缀的转换

在研究如何将中缀转换为后缀表示法之前，我们需要考虑以下中缀表达式求值的基本知识。

  • 中缀表达式的求值从左到右开始。

  • 记住优先级，例如 * 的优先级高于 +。例如

    • 2+3*4 = 2+12.

    • 2+3*4 = 14.

  • 使用括号覆盖优先级，例如

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

    • (2+3)*4= 20.

现在让我们手动将简单的中缀表达式 A+B*C 转换为后缀表达式。

Sr.No Character读 中缀表达式解析至此 后缀表达式开发至此 备注
1 A A A
2 + A+ A
3 B A+B AB
4 * A+B* AB + 无法复制，因为 * 具有更高的优先级。
5 C A+B*C ABC
6 A+B*C ABC* 复制 *，因为有两个操作数 B 和 C
7 A+B*C ABC*+ 复制 +，因为有两个操作数 BC 和 A

现在让我们使用堆栈将上面的中缀表达式 A+B*C 转换为后缀表达式。

Sr.No 读取的字符 到目前为止解析的中缀表达 到目前为止开发的后缀表达式 堆栈内容 备注
1 A A A
2 + A+ A + 将 + 运算符推送到堆栈中。
3 B A+B AB +
4 * A+B* AB +* 运算符 * 的优先级高于 +。将 * 运算符推送到堆栈中。否则，+ 会弹出。
5 C A+B*C ABC +*
6 A+B*C ABC* + 没有更多操作数，弹出 * 运算符。
7 A+B*C ABC*+ 弹出 + 运算符。

现在让我们看另一个示例，通过使用堆栈将中缀表达式 A*(B+C) 转换为后缀表达式。

Sr.No 读取的字符 到目前为止解析的中缀表达 到目前为止开发的后缀表达式 堆栈内容 备注
1 A A A
2 * A* A * 将 * 运算符推送到堆栈中。
3 ( A*( A *( 将 ( 推送到堆栈中。
4 B A*(B AB *(
5 + A*(B+ AB *(+ 将 + 压入堆栈。
6 C A*(B+C ABC *(+
7 ) A*(B+C) ABC+ *( 弹出 + 运算符。
8 A*(B+C) ABC+ * 弹出 ( 运算符。
9 A*(B+C) ABC+* 弹出其余运算符。

示例

现在我们将演示如何使用堆栈将中缀表达式转换为后缀表达式，然后计算后缀表达式。

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

//字符堆栈
char stack[25]; 
int top=-1; 

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

//返回运算符的优先级
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; 
   }
}

//检查符号是否为运算符？
int isOperator(char symbol) { 
   switch(symbol){ 
      case '+': 
      case '-': 
      case '*': 
      case '/': 
      case '^': 
      case '(': 
      case ')':
         return 1; 
      break; 
         default:
         return 0; 
   } 
}
//将中缀表达式转换为后缀表达式
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
" , infix);
   printf("Postfix expression is: %s
" , postfix);
   printf("Evaluated expression is: %d
" , evaluate(postfix));
}

输出

如果我们编译并运行上述程序，则会产生以下输出 −

Infix expression is: 1*(2+3)
Postfix expression is: 123+*
Result is: 5
❮ 上一节 下一节 ❯