表达式解析

表达式解析 首页 / 结构和算法入门教程 / 表达式解析

编写算术表达式的方式称为符号,算术表达式可以用三种不同但等效的符号表示。这些符号是-

  • 前缀表达式
  • 中缀表达式
  • 后缀表达式

这些符号被命名为它们如何在表达式中使用运算符。在本章中,我们将学习相同的内容。

前缀表达法

在这种表示法中,运算符以操作数为前缀,即运算符被写在操作数之前。例如,+ ab。这等效于其后缀符号​​a + b,前缀表示法也称为波兰表示法。

中缀表达式

我们用中缀表示法来编写表达式,例如a-b + c,其中在操作数之间使用运算符。对于人类来说,以中缀符号进行阅读,书写和说话很容易,但是在计算设备上却不能很好地兼容,就时间和空间消耗而言,用于处理中缀表示法的算法可能是困难且昂贵的。

后缀表达式

这种表示法样式称为反向波兰表示法。在这种表示方式中,运算符后缀到操作数之后,即运算符写在操作数之后。例如 ab + 这等效于其后缀符号​​a + b。

无涯教程网

链接:https://www.learnfk.comhttps://www.learnfk.com/data-structures-algorithms/expression-parsing.html

来源:LearnFk无涯教程网

下表简要三种表示法的区别-

Sr.No.中缀前缀后缀
1a + b+ a ba b +
2(a + b) ∗ c∗ + a b ca b + c ∗
3a ∗ (b + c)∗ a + b ca b c + ∗
4a/b + c/d+/a b/c da b/c d/+
5(a + b) ∗ (c + d)∗ + a b + c da b + c d + ∗
6((a + b) ∗ c) - d- ∗ + a b c da b + c ∗ d -

后缀判断算法

现在,我们将研究有关如何判断后缀表示法的算法-

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

祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)

技术教程推荐

程序员的数学基础课 -〔黄申〕

Go语言从入门到实战 -〔蔡超〕

Netty源码剖析与实战 -〔傅健〕

雷蓓蓓的项目管理实战课 -〔雷蓓蓓〕

正则表达式入门课 -〔涂伟忠〕

Selenium自动化测试实战 -〔郭宏志〕

程序员的个人财富课 -〔王喆〕

如何讲好一堂课 -〔薛雨〕

搞定音频技术 -〔冯建元 〕

好记忆不如烂笔头。留下您的足迹吧 :)