编写算术表达式的方式称为符号,算术表达式可以用三种不同但等效的符号表示。这些符号是-
这些符号被命名为它们如何在表达式中使用运算符。在本章中,我们将学习相同的内容。
在这种表示法中,运算符以操作数为前缀,即运算符被写在操作数之前。例如,+ 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. | 中缀 | 前缀 | 后缀 |
---|---|---|---|
1 | a + b | + a b | a b + |
2 | (a + b) ∗ c | ∗ + a b c | a b + c ∗ |
3 | a ∗ (b + c) | ∗ a + b c | a b c + ∗ |
4 | a/b + c/d | +/a b/c d | a b/c d/+ |
5 | (a + b) ∗ (c + d) | ∗ + a b + c d | a b + c d + ∗ |
6 | ((a + b) ∗ c) - d | - ∗ + a b c d | a b + c ∗ d - |
现在,我们将研究有关如何判断后缀表示法的算法-
#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
祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)