当前位置：文档之家 › 中缀表达式求值

中缀表达式求值

  • 格式：doc
  • 大小：138.00 KB
  • 文档页数：12

江西理工大学软件学院计算机类课程实验报告课程名称：数据结构班级：11软件会计4班姓名：黄健学号：11222122江西理工大学软件学院一、目录（中缀表达式求值）1、目录--------------------------------------------------------------22、实验目的--------------------------------------------------------33、实验要求--------------------------------------------------------34、实验仪器设备与材料-----------------------------------------35、实验原理--------------------------------------------------------46、实验步骤--------------------------------------------------------57、实验原始记录--------------------------------------------------68、实验数据分析计算结果--------------------------------------109、实验心得体会--------------------------------------------------1110、思考题----------------------------------------------------------12二：实验目的：对一个合法的中缀表达式求值。

简单起见，假设表达式只包含+，-，*，÷等4个双目运算符，且运算符本身不具有二义性，操作数均为一位数整。

三：要求：1、正确解释表达式2、符合四则运算规格3、输出最后的计算结果四：实验仪器设备与材料参考书籍电脑及其配件Microsoft Visulai C++ 6.0五：实验原理对中缀表达式求值，通常使用“酸腐优先算法”。

根据四则运算规则，在运算的每一步中，任意两个相继出班的运算符t和c之间的优先关系至多是下面三种关系之一：1、t的优先级低于c2、t的优先级高于c3、t的优先级高于c为实现算符优先算法，可以使用两个工作栈：一个栈存放运算符；另一个栈存放操作数，中缀表达式用一个字符串数组存储。

六：实验步骤1、基本操作：Initialization()操作结果：构造链栈tran()初始条件：链栈已经存在操作结果：将中缀表达式转化为后缀表达式Sum()初始条件：链栈已经存在并且中缀表达式已经转化为后缀表达式操作结果：求出表达式的值2、程序包括三个模块：（1）装程序模块（2）构造链栈模块（3）表达式转换模块（4）表达式求职模块最后测试数据：输入表达式，以#结束：后缀表达式为：输出后缀表达式计算结果为：输出计算结果七：实验原始记录s truct node{char datat;int num;struct node*next;};V oid main(){Struct node*top,*head;Top=initialization();Printf("请输入表达式，以#结束：\n");Gets(stringl);Head=tran(top);Sum(head);}Struct node*initialization(){Struct node*top；Top=(struct node*)malloc(sizeof(struct node));Top->data='';Top->num=0;Top->next=NULL；Return top;}Struct node*p,*top;Int i;To p=s;Int m;Char a;M=strlen(string1);For(i=0;i<=m;i++){a=string1[i];If('0'<=string1[i]&&string1[i]<='9'){String2[j]=string1[i];j++;}Else{Swith(a){Case'(':{P=(struct node*)malloc(sizeof(struct node));P->data=a;p->next=top;Top=p;Break;}case'*':case'/':String2[j]=' ';j++;If((top->data=='*')||(top->data=='/')){String2[j]=top->data;j++;Top->data=a;Break;}Else{P=(struct node*)malloc(sizeof(struct node));P->data=a;p->next=top;Top=p;Break;}Case'+':Case'-':{String2[j]=' ';j++;If(top->data=='+'||top->data=='*'||top->data=='/'){String2[j]=top->data;j++;Top->data=a;Break:}}Case')':{String2[j]=' ';j++;If(top->data=''){printf("input error");break;)While(top->data!='('){String2[j]=top->data;j++;P=top;Top=top->next;Free(p):}P=top;top=->next;free(p);Break;}}}}While(top->data!=''){String2[j]=top->data;j++;P=top;Top=top->next;Free(p);}String2[j]='#';Printf(后缀表达式为：\n");For(i=0;i<j;i++)If(string2[i]!=' ')Printf("%c",string2[i]);Printf("\n");Return top;}Struct node *sum(struct node *s){Struct node *top,*p;Char *q;Int x,y,a;Int i,n;Top=s;For(i=0;i<=j;i++){If(string2[i]>='0'&&string2[i]<='9'){Q=&string2[i];A=atoi(q);For(n=i;string2[n]>='0'&&string2[n]<='9';n++){}P=(struct node *)malloc(sizeof(struct node ));P->num=a;p->next=top;top=p;I=n-1;}ElseIf(string2[i]=='#')Printf("计算结果为：\n%d\n",top->num);Else{If(string2[i]==' '){}Else{Y=top->num;p=top;top=top->next;free(p);X=top->num;p=top;top=top->next;free(p);Switch(string2[i]){case'+':{a=x+y;P=(struct node *)malloc(sizeof(struct node));P->num=a;p->next=top;top=p;Break;}Case'-':{a=x-y;P=(struct node *)malloc(sizeof(struct node ));P->num=a;p->next=top;top=p;Break;}Case'-':{a=x-y;P=(struct node *)malloc(sizeof(struct node ));P->num=a;p->next=top;top=p;Break;}Case'*':{a=x*y;P=(struct node *)malloc(sizeof(struct node ));P->num=a;p->next=top;top=p;Break;}Case'/':{if(y==0)Printf("ERROR:除数为零！\n");A=(float)x/y:P=(struct node *)malloc(sizeof(struct node ));P->num=a;p->next=top;top=p;Break;}}}}}Return o;}八：实验数据分析计算结果第一组：输入：中缀表达式为：1+2*3+4#输出：后缀表达式为：123*+4+，计算结果为11 第二组：输入：中缀表达式为：1+2*（3+4）+5#输出：后缀表达式为：1234+*+5+，计算结果为20分析正确。

九：实验心得、体会这次实验设计让我更加了解大一学到的 C 和这个学期学到的数据结构.课设题目要求不仅要求对课本知识有较深刻的了解, 同时要求程序设计者有较强的思维和动手能力和更加了解编程思想和编程技巧. 这次课程设计让我有一个深刻的体会,那就是细节决定成败,编程最需要的是严谨, 如何的严谨都不过分,往往检查了半天发现错误发生在某个括号,分号,引号,或者数据类型上。

实验设计时, 也不要怕遇到错误, 在实际操作过程中犯的一些错误还会有意外的收获, 感觉实验设计很有意思。

在具体操作中这学期所学的数据结构的理论知识得到巩固, 达到实验设计的基本目的,也发现自己的不足之出,在以后的上机中应更加注意,同时体会到 C 语言具有的语句简洁,使用灵活,执行效率高等特点.发现上机的重要作用,特别算术表达式有了深刻的理解。

合集下载

c++ 中缀表达式

c++ 中缀表达式

c++ 中缀表达式
C++ 中缀表达式（Infix Expression）是指运算符位于操作数之
间的表达式，例如：a + b * c。

在C++中，中缀表达式的求值需要遵循运算符的优先级和结
合性规则。

一般来说，乘法、除法、取模运算的优先级最高，加法、减法运算的优先级较低。

在编写C++程序时，为了正确求解中缀表达式，可以使用以
下方法之一：
1. 使用栈进行中缀表达式的转换和求解。

2. 使用递归函数或逆波兰表达式将中缀表达式转换成后缀表达式，然后使用栈进行后缀表达式的求解。

例如，给定中缀表达式 a + b * c，可以使用栈的方法求解：
1. 创建一个空栈用于存储运算符和操作数。

2. 遍历中缀表达式的每个字符，按以下规则处理：
- 如果遇到操作数，则将其压入栈中。

- 如果遇到运算符，则根据其优先级和结合性，判断是否需
要将运算符从栈中弹出并进行运算。

然后将运算结果压入栈中。

- 如果遇到左括号，则直接将其压入栈中。

- 如果遇到右括号，则取出栈中的运算符和操作数，直到遇
到左括号为止，并进行相应的运算。

最后将运算结果压入栈中。

3. 遍历完中缀表达式后，栈中最后一个元素即为表达式的结果。

注：以上只是一种求解中缀表达式的方法，实际求解方法可能有其他的实现方式。

关于中缀表达式求值（四则运算和括号，支持多位数）

关于中缀表达式求值（四则运算和括号，支持多位数）

关于中缀表达式求值（四则运算和括号，⽀持多位数）1.中缀转后缀和计算后缀表达式 1.1 中转后1. 数字则输出2. 如果是 "(" ,直接⼊栈3. 如果是 ")", 栈顶元素出栈并输出，直到遇到" ("，只弹出。

4. 如果栈空，直接⼊栈，否则和栈顶⽐较优先级，当⼤于栈顶时，⼊栈，否则，栈顶元素退栈，直到⼤于栈顶或栈空5. 中缀表达式扫描完毕，若栈不空，将其内所有元素弹出。

1.2 计算后缀1. 数字则⼊栈2. 运算符，出栈b,再出栈a 计算c=a operate b,将c⼊栈3. 中缀表达式扫描完毕，将栈内唯⼀的元素（也就是求的值）弹出并返回。

2.代码如下import java.util.*;import java.util.regex.Matcher;import java.util.regex.Pattern;;public class Test4 {private static Map<Character,Integer> map=new HashMap<>();static {map.put('+', 0);map.put('-', 0);map.put('*', 1);map.put('/', 1);}private static List<String> toPost(String target){List<String> post=new ArrayList<>();Stack<Character> stk=new Stack<>();Pattern p=pile("\\d+|\\D");Matcher m=p.matcher(target);while(m.find()) {String e=m.group();if(e.matches("\\d+"))post.add(e);else if(e.equals("("))stk.push('(');else if(e.equals(")")){while(stk.peek()!='(')post.add(stk.pop()+"");stk.pop();}else {char op=e.charAt(0);while(!stk.isEmpty()&&stk.peek()!='('&&map.get(op)<=map.get(stk.peek()))post.add(stk.pop()+"");stk.push(op);}}while(!stk.isEmpty()) post.add(stk.pop()+"");return post;}private static int calcuPost(List<String> post) {Stack<Integer> stk=new Stack<>();for(String s:post) {if(s.matches("\\d+")) stk.push(Integer.parseInt(s));else {char c=s.charAt(0);int b=stk.pop();int a=stk.pop();int t=0;if(c=='+')t=a+b;else if(c=='-')t=a-b;else if(c=='*')t=a*b;elset=a/b;stk.push(t);}}return stk.pop();}public static void main(String[] args) {Scanner is=new Scanner(System.in);while(is.hasNext()) {String exp=is.next();System.out.println(calcuPost(toPost(exp))); }is.close();}}。

表达式求值算法总结(C++)

表达式求值算法总结(C++)

表达式求值算法总结(C++)表达式求值，一般采用栈和队列的方式来求值，下面介绍表达式求值的两种算法。

方法一、使用两个栈，一个为操作符栈OPTR(operator)，一个是操作数栈OPND(operand)算法过程：当输入3 * ( 4 - 1 * 2 ) + 6 / ( 1 + 1 )时，为简单方便，我们输入时，按照字符的顺序一个一个的处理，比如ch = getchar()。

然后根据ch 的值判断：若ch 是数字，直接压入操作数栈OPND；若ch 是'('，直接入栈OPTR;若ch 是')'，若OPTR 和OPND 非空，弹出OPTR的栈顶操作符，弹出OPND栈顶的两个操作数，做运算，然后见个结果压入栈OPND，直到弹出的OPTR栈顶元素时')';若ch 是操作符(比如+, -, *, /)，如果OPTR栈顶元素是(，直接入栈OPTR，如果不是'('且OPTR栈非空且栈顶元素操作符的优先级大于ch，那么弹出OPTR的栈顶操作符，并弹出OPND中栈顶的两个元素，做运算，将运算结果入栈OPND，此时，重复这一步操作；否则将ch入栈OPTR；若ch为EOF，说明表达式已经输入完成，判断OPTR是否为空，若非空，一次弹出OPTR 栈顶操作符，并与OPND栈顶两个元素做运算，将运算结果入栈OPND，最后表达式的结果即OPND的栈底元素。

以表达式3 * ( 4 - 1 * 2 ) + 6 / ( 1 + 1 )为例，计算过程如下所示：通过上述的计算过程，写出伪代码如下所示：void GetExpress(Stack * OPTR, Stack * OPND){char ch;while ((ch = getchar ()) != EOF) {if (IsDigit (ch)) {PushStack (OPND, ch);}else if (ch == '(')PushStack (OPTR, ch);else if (ch == ')') {while (!IsStackEmpty(OPTR)) {PopStack (OPTR, op);if (op == ')')break;PopStack (OPND, num2);PopStack (OPND, num1);res = Calc (num1, num2, op);PushStack (OPND, res);}}else if (ch == '+' || ch == '-'|| ch == '*' || ch == '/') {while (!IsStackEmpty (OPTR) && GetTop (OPTR)!='(' && GetTop (OPTR)>ch) { PopStack (OPTR, op);PopStack (OPND, num2);PopStack (OPND, num1);res = Calc (num1, num2, op);PushStack (OPND, res);}if (IsStackEmpty (OPTR) || GetTop(OPTR)=='(')PushStack (OPTR, ch);}}}// 当表达式输入完成后，需要对OPTR栈和OPND中的元素进行运算int GetValue(Stack * OPTR, Stack * OPND){while (!IsStackEmpty (OPTR)) {PopStack (OPTR, op);PopStack (OPND, num2);PopStack (OPND, num1);res = Calc (num1, num2, op);PushStack (OPND, res);}// 最后的操作数栈OPND栈顶元素即是表达式的值return GetTop(OPND);}PS: 上面没有指出表达式非法的情况方法二：采用中缀表达式的方法，求取表达式的中缀表达式，借用一个操作符栈OPTR和中缀表达式队列Queue，求取中缀表达式，然后对中缀表达式求值。

中缀表达式求值

中缀表达式求值

中缀表达式求值所⽤知识：C语⾔，堆栈操作算法思想来⾃慕课浙江⼤学《数据结构》陈⽼师，何⽼师笔记：1.堆栈：1.1 引⼦⼀种数据结构，在函数调⽤，表达式求值等都有⼴泛的应⽤中缀表达式：a+b*c-d/e:⽣活中经常使⽤，但是计算机不好识别后缀表达式：abc*+dc/-:⽣活中不好使⽤，但计算机容易识别例：总结：因此需要⼀种存储⽅法，能顺序的存储运算数，在需要时倒叙输出。

-->堆栈有堆栈的特点：后⼊先出。

1.2堆栈的操作操作集：长度为maxSize的堆栈S ==> stack,堆栈的元素elementType，那么如下的操作stack createStack(int maxSize);//⽣成空堆栈，其最⼤长度为maxSizeint isFull(stack s,int maxSize);//判断栈s是否为空void push(stack s,elementType item);//将元素压⼊堆栈int isEmpty(stack s);//判断堆栈是否为空elementType pop(stack s);//删除并返回栈顶元素1.2.1⽤数组来表⽰堆栈的⽅法可以参照⽂件夹下⾯的同级⽬录的⽂件stackArray.c同时还有使⽤⼀个数组来表⽰两个堆栈，twoStack.c1.2.2使⽤链表来模拟堆栈因为链表有两头，但是堆栈的头指针我们会选择链表的头节点，因为便于删除操作，尾节点不⽅便进⾏删除操作下⾯是模拟的⽰意图head(头指针，没有元素的) --> node1(top指针) --> node2(堆栈中的元素) --> node3 --> node4代码可以见：stackLinkList.c1.2.3 利⽤堆栈进⾏表达式求值我们平时所见到的表达式都是中缀表达式，但是如果想求表达式的值，先把中缀表达着中⽂后缀表达式，在利⽤堆栈对后缀表达式进⾏求值中缀表达式转后缀表达式的思路；⾸先看⼀个简单的：中缀表达式：2 + 9 / 3 - 5 后缀表达式：2 9 3 / + 5 -通过对⽐我们发现，中缀表达式和后缀表达式的数字顺序并没有发⽣改变，只是符号位置发⽣了改变所以，我们可以构思，使⽤⼀个栈来存在运算符，遇到数字就输出，遇到符号就压栈，如果读⼊的符号⽐栈顶的符号优先级⾼，就压栈，否则就弹栈并输出下⾯是中缀表达式：2 + 9 / 3 - 5压栈和弹栈的具体步骤输出堆栈内元素2+9/(优先级⽐+⾼，压栈)3/ + -(⾸先弹出/,但是因为同级运⾏需要按照从左往右的运算，所以+也需要弹栈)5 -- (元素全部读取完毕以后，-弹栈)所以中缀表达式：2 + 9 / 3 - 5的后缀表达式为 2 9 3 / + 5 -但是如果遇到带有()的表达式怎么办：遇到"("把"("压⼊栈中，此时栈中的"("运算级别最低，在按照上⾯的运算符的运算规则来进⾏压栈和弹栈。