表达式求值

表达式求值的类型定义与操作实现一、需求分析设计一个程序，演示用算符优先法对算术表达式求值的过程。

利用算符优先关系，实现对算术四则混合运算表达式的求值。

（1）输入的形式：表达式，例如2*(3+4)#；包含的运算符只能有'+' 、'-' 、'*' 、'/' 、'('、')'；（2）输出的形式：运算结果，例如Answer is:77.000000；（3）程序所能达到的功能：对表达式求值并输出结果。

二、概要设计：本课程设计需要用到抽象数据类型栈存储表达式。

本部分给出栈的类型定义与表达式求值操作描述。

1、存储结构（顺序栈）：typedef struct SqStack{SElemType *base;SElemType *top;int stacksize;}SqStack;2、基本操作：Status InitStack(SqStack &s)操作结果：初始化一个空栈s。

Status GetTop(SqStack s,SElemType &e)初始条件：栈s已存在。

操作结果：得到s的栈顶元素并用e带回。

Status Push(SqStack &s,SElemType e)初始条件：栈s已存在。

操作结果：向栈s中压入元素e。

Status Pop(SqStack &s,SElemType &e)初始条件：栈s已存在‘操作结果：弹出栈s栈顶元素，并用e带回。

Status In(char e)操作结果：判断e是否为7种运算符之一char Precede(char p,char c)操作结果：比较运算符p与运算符c的优先级。

SElemType Operate(SElemType x,char n,SElemType y)操作结果：计算x,y对运算符n的运算结果。

三、详细设计本部分主要给出表达式求值的实现算法1、初始化一个空栈sStatus InitStack(SqStack &s) //{s.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!s.base)exit(OVERFLOW);s.top=s.base;s.stacksize=STACK_INIT_SIZE;return OK;}2、读取栈顶元素Status GetTop(SqStack s,SElemType &e){if(s.top==s.base)return ERROR;e=*(s.top-1);return OK;}3、向栈s中压入元素eStatus Push(SqStack &s,SElemType e){if(s.top-s.base>=s.stacksize){s.base=(SElemType*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;}*s.top++=e;return OK;}4、弹出栈顶元素Status Pop(SqStack &s,SElemType &e) //{if(s.top==s.base)exit(OVERFLOW);e=* --s.top;return OK;}5、判断是否为7种运算符之一Status In(char e) / /{switch(e){case '+':case '-':case '*':case '/':case '(':case ')':case '#':return(1);break;default:return(0);}}6、比较两运算符优先级char Precede(char p,char c){ 'switch(p){case '+':case '-':switch(c){case '*':case '/':case '(':return '<';break;default:return '>';break;}break;case '*':case '/':switch(c){case '(':return '<';break;default:return '>';break;}break;case '(':switch(c){case ')':return '=';break;case '#':printf("ERROR!!\n");exit(OK);default:return '<';break;}break;case ')':switch(c){case '(':printf("ERROR!!\n");exit(OK);default:return '>';break;}break;case '#':switch(c){case ')':printf("ERROR!!\n");exit(OK);case '#':return '=';break;default:return '<';break;}break;}}7、四则运算SElemType Operate(SElemType x,char n,SElemType y) {SElemType e;switch(n){case '+':e=x+y;break;case '-':e=x-y;break;case '*':e=x*y;break;case '/':if(y==0){printf("分母不能为0！\n");exit(1);}else{e=x/y;break;}}return e;}8、主函数进行表达式求值void main(){SqStack OPTR,OPND;SElemType p,s,a,b,theta;char c;printf("请输入一个表达式并以'#'结束\n(只包括' +-*/' 和'('')'):\n");InitStack(OPTR);Push(OPTR,'#');InitStack(OPND);c=getchar();GetTop(OPTR,p);while(c!='#'||p!='#'){if(!In(c)){s=c-48;c=getchar();while(c>='0'&&c<='9'){s=s*10+(c-48);c=getchar();}Push(OPND,s);}else{switch(Precede(p,c)){case '<':Push(OPTR,c);c=getchar();break;case '=':Pop(OPTR,s);c=getchar();break;case '>':Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}GetTop(OPTR,p);}}//whileprintf("\n\n");GetTop(OPND,p);printf("Answer is:%f\n",p);getch();}四、调试分析1、初始化了一种类型的两个栈，分别用来存放数值和运算符。

表达式求值算法总结(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，求取中缀表达式，然后对中缀表达式求值。

字符串表达式求值（⽀持多种类型运算符）⼀、说明1. 输⼊字符串为中缀表达式，⽆需转为后缀表达式2. ⽀持的运算符包括：算术运算符："+,-,*,/"关系运算符：">,<,>=,<=,=,!="(注意等于运算符采⽤的是⼀个等号)逻辑运算符："&&,||"3. ⽀持⼤于10的数字，不⽀持负数操作数，但⽀持中间结果和返回值为负数⼆、算法原理&步骤本⽂算法对中缀表达式形式字符串进⾏求值，同时⽀持与或运算和逻辑运算(若含有关系运算符或者逻辑运算符，则输出为1或者0)。

类似于加减乘除，将关系运算符和逻辑运算符看作优先级低的运算符进⾏处理，优先级：算术运算符>关系运算符>逻辑运算符。

步骤：1. 初始化两个空堆栈，⼀个存放操作数，⼀个存放运算符。

2. 从左⾄右扫描输⼊字符串，依次读取。

2.1 若为操作数，则压⼊操作数栈；2.2 若为运算符，判断其优先级是否⼤于运算符栈栈顶元素优先级。

若⼤于栈顶元素优先级，则直接压栈；否则，弹出栈顶元素operator，同时依次从操作数栈中弹出两个元素number1,number2，计算表达式(number2 operator number1)的值value，并将值value压⼊操作数栈。

重复上述过程直⾄当前扫描的操作符优先级⼤于栈顶元素，然后将当前运算符压栈。

3. 弹出运算符栈顶元素operator，同时依次从操作数栈中弹出两个元素number1,number2，计算表达式(number2 operator number1)的值value，并将值value压⼊操作数栈。

重复上述过程直⾄运算符栈为空。

4. 此时操作数栈应该只有⼀个元素，即为表达式的值。

三、代码&测试求值函数：1/* 字符串表达式求值2 * @param input: 输⼊的字符串3 * @param output: 表达式的值，若含有关系运算符则为1或者04 * return 计算过程是否正常5*/6bool ExpValue(string input,int& output)7 {8 stack<int> operand_stack;9 stack<string> operator_stack;1011char prev = 0; // 上⼀个属于运算符的字符12for (int i = 0; i < input.size(); i++)13 {14char c = input[i];15// prev是否是⼀个完整运算符16if (!isOperator(c) && prev)17 {18string new_op = string("").append(1, prev);19 addNewOperator(new_op, operand_stack, operator_stack);20 prev = 0;21 }2223// 数字24if (isdigit(c))25 {26int val_c = c - '0';27if (i > 0 && isdigit(input[i - 1]))28 {29int top_num = operand_stack.top();30 top_num = top_num * 10 + val_c;31 operand_stack.pop();32 operand_stack.push(top_num);33 }34else35 operand_stack.push(val_c);36 }37// 运算符字符38else if (isOperator(c))39 {40// 处理两字符运算符41if (prev)42 {43string new_op = string("").append(1, prev).append(1, c);44 addNewOperator(new_op, operand_stack, operator_stack);45 prev = 0;46 }47else48 prev = c;49 }50else if (c == '(')51 operator_stack.push("(");52else if (c == ')')53 {54// 处理括号内的运算符55while (operator_stack.top()!="(")56 {57int num1 = operand_stack.top();58 operand_stack.pop();59int num2 = operand_stack.top();60 operand_stack.pop();61string op = operator_stack.top();62 operator_stack.pop();6364int val = Calculate(num2, num1, op);65 operand_stack.push(val);66 }67 operator_stack.pop(); // 弹出"("68 }69 }70 assert(operand_stack.size() == operator_stack.size() + 1);71// 弹出所有运算符72while(!operator_stack.empty())73 {74int num2 = operand_stack.top();75 operand_stack.pop();76int num1 = operand_stack.top();77 operand_stack.pop();78string op = operator_stack.top();79 operator_stack.pop();8081int val = Calculate(num1, num2, op);82 operand_stack.push(val);83 }8485if (operand_stack.size() == 1) {86 output = operand_stack.top();87return true;88 }89return false;90 }其中⽤到的⼦函数有：/* 判断字符是否属于运算符 */bool isOperator(char c){switch (c){case'-':case'+':case'*':case'/':case'%':case'<':case'>':case'=':case'!':case'&':case'|':return true;default:return false;}}/* 获取运算符优先级 */int getPriority(string op){int temp = 0;if (op == "*" || op == "/" || op == "%")temp = 4;else if (op == "+" || op == "-")temp = 3;else if (op == ">" || op == "<" || op == ">=" || op == "<="|| op == "=" || op == "!=")temp = 2;else if (op == "&&" || op == "||")temp = 1;return temp;}/** 返回⼀个两元中缀表达式的值* syntax: num_front op num_back* @param num_front: 前操作数* @param num_back: 后操作数* @param op: 运算符*/int Calculate(int num_front, int num_back, string op){if (op == "+")return num_front + num_back;else if (op == "-")return num_front - num_back;else if (op == "*")return num_front * num_back;else if (op == "/")return num_front / num_back;else if (op == "%")return num_front % num_back;else if (op == "!=")return num_front != num_back;else if (op == ">=")return num_front >= num_back;else if (op == "<=")return num_front <= num_back;else if (op == "=")return num_front == num_back;else if (op == ">")return num_front > num_back;else if (op == "<")return num_front < num_back;else if (op == "&&")return num_front && num_back;else if (op == "||")return num_front || num_back;return0;}/* 新运算符⼊栈操作 */void addNewOperator(string new_op, stack<int>& operand_stack, stack<string>& operator_stack) {while (!operator_stack.empty() && getPriority(operator_stack.top()) >= getPriority(new_op)){int num2 = operand_stack.top();operand_stack.pop();int num1 = operand_stack.top();operand_stack.pop();string op = operator_stack.top();operator_stack.pop();int val = Calculate(num1, num2, op); operand_stack.push(val);}operator_stack.push(new_op);}View Code测试结果：int main(){string s0 = "10-1*10+3%2";string s1 = "100 + (3-33)*2";string s2 = "20+1 >= 20 && 20+1 < 20"; string s3 = "10>20 || 10/1>=5";int ret = -1;if (ExpValue(s0, ret))cout << s0 << "的值: " << ret << endl; if (ExpValue(s1, ret))cout << s1 << "的值: " << ret << endl; if (ExpValue(s2, ret))cout << s2 << "的值: " << ret << endl; if (ExpValue(s3, ret))cout << s3 << "的值: " << ret << endl; return0;}上述代码的执⾏结果为：。

ＸＸXＸXX大学《数据结构》课程设计报告班级：学号：姓名：指导老师:目录一算术表达式求值一、需求分析二、程序得主要功能三、程序运行平台四、数据结构五、算法及时间复杂度六、测试用例七、程序源代码二感想体会与总结算术表达式求值一、需求分析一个算术表达式就是由操作数(oｐeranｄ）、运算符(operator）与界限符（deｌimiter)组成得。

假设操作数就是正整数，运算符只含加减乘除等四种运算符,界限符有左右括号与表达式起始、结束符“#”，如：＃(7+15）*（2３—２8/４）#。

引入表达式起始、结束符就是为了方便.编程利用“算符优先法”求算术表达式得值.二、程序得主要功能（1）从键盘读入一个合法得算术表达式，输出正确得结果。

(2）显示输入序列与栈得变化过程。

三、程序运行平台Ｖｉsｕaｌ C＋+6、0版本四、数据结构本程序得数据结构为栈。

（1）运算符栈部分：struct SqStaｃk ／/定义栈{char *base； //栈底指针ｃｈａr *toｐ; ／/栈顶指针inｔstacｋsiｚe； //栈得长度};inｔInitSｔack (SqＳｔack &ｓ) //建立一个空栈S{ｉf （!(s、ｂａse= (char ＊）ｍalloc(5０＊ｓizeof（chａr）)）)exｉt（0）；ｓ、ｔop=s、bａse;s、staｃksiｚｅ=５0；retuｒn OK；}ｃhar GeｔTop（SqStack s,char &e) /／运算符取栈顶元素｛iｆ (s、ｔop==s、ｂase) //栈为空得时候返回EＲROR｛ﻩ prｉntf(＂运算符栈为空！＼n")；ﻩ reｔurn ERＲＯR;｝elsee＝*（s、ｔoｐ-1); //栈不为空得时候用ｅ做返回值，返回S得栈顶元素，并返回OK returnＯＫ;｝ｉnt Push(SqStacｋ＆s，cｈａr ｅ） //运算符入栈｛if （s、tｏp—s、baｓe >= ｓ、ｓtacksｉzｅ）ﻩ{ｐriｎtf（＂运算符栈满!＼n"）;ﻩs、basｅ=（cｈaｒ*）reａlloｃ(s、bａｓe，(s、sｔackｓｉze+5)*ｓizeoｆ(cｈar））；//栈满得时候,追加5个存储空间ｉf(！s、basｅ)exｉt （OVERＦＬOW）；s、top=s、ｂａsｅ+s、ｓｔacｋsize;s、ｓtaｃksiｚｅ+=５;}ﻩ＊(s、ｔop）＋＋=e；／/把e入栈ﻩｒeturn OK;}ｉnｔ Pop(SqStaｃk &ｓ，char ＆ｅ） /／运算符出栈｛ｉｆ (s、toｐ==s、base) ／/栈为空栈得时候，返回ERＲOＲ｛ｐrintf（＂运算符栈为空!\n”）;ﻩ return ERROＲ;}else｛ﻩﻩe=＊-—ｓ、tｏp；/／栈不为空得时候用e做返回值，删除S得栈顶元素，并返回ＯK return OK；}}iｎt StackTｒaｖerse（ＳqStacｋ&ｓ)／/运算符栈得遍历｛ﻩchar ＊t；ﻩt=s、ｂａｓｅ；ﻩif (s、top＝=s、baｓe）｛ﻩ printｆ（”运算符栈为空！\ｎ”)； //栈为空栈得时候返回ＥＲRORｒeturn ERＲOＲ;}ｗhile（t！＝s、tｏp)｛ﻩﻩｐrｉｎｔf（" %c",＊t)； //栈不为空得时候依次取出栈内元素t++;ﻩ}ｒeturｎ EＲRＯR；｝（2）数字栈部分：strｕｃt SqSｔackn//定义数栈｛ｉnt *bａse; //栈底指针ｉnt＊tｏp； //栈顶指针ｉnｔ sｔacksｉze； //栈得长度｝;inｔIｎｉtStackｎ (SqSｔackn &s) //建立一个空栈Ｓ{s、base=（int＊）malｌoc（50*sｉzeof(int）);if(！ｓ、ｂase）eｘiｔ（OVEＲFLＯW）；//存储分配失败s、top=s、base；s、stacksizｅ=5０;reｔuｒn OK；｝ｉｎt GｅtToｐn(ＳqＳtａcｋn s,inｔ＆e) //数栈取栈顶元素{if（s、ｔop=＝s、base）{prinｔｆ(＂运算数栈为空!\ｎ＂);//栈为空得时候返回ERRORﻩ rｅturｎ ERROR;}eｌseﻩe＝＊（s、toｐ-1);／/栈不为空得时候，用e作返回值，返回S得栈顶元素，并返回OＫreturｎＯK；｝int Pｕshn（SｑStａckn ＆s，int ｅ) //数栈入栈｛if（s、tｏp—s、ｂasｅ＞＝s、stacksiｚe)｛ﻩﻩprｉｎｔf（"运算数栈满!\ｎ"）；／/栈满得时候,追加5个存储空间ﻩs、base=(int＊）realloc (s、baｓe,(s、stａcksize＋5)＊sｉzｅof（ｉnt));ｉf（!s、base) ｅxit (ＯＶERFLOW)；ﻩs、top=ｓ、bａsｅ＋ｓ、stacｋsize;//插入元素e为新得栈顶元素s、stacksｉｚe+=5；}*（s、top）++=e; /／栈顶指针变化returｎOK;}ｉｎt Popｎ(ＳｑSｔacｋn ＆s，iｎt &e)//数栈出栈｛ﻩif （s、top=＝ｓ、base）｛ﻩ pｒiｎtｆ（"运算符栈为空！\n＂);//栈为空栈得视时候，返回ERRＯＲﻩ retｕrn ERROR；ﻩ｝ｅlse｛ﻩﻩe=＊—-ｓ、tｏp；／/栈不空得时候，则删除S得栈顶元素,用e返回其值，并返回OK ﻩreturｎOK；｝}ｉnt StacｋＴraveｒsｅn（SqStackn &s)/／数栈遍历{ﻩiｎｔ＊t;ﻩｔ=s、basｅ ;ﻩif（s、top==s、basｅ）ﻩ｛pｒinｔf(＂运算数栈为空！\n”）；//栈为空栈得时候返回ERRORﻩ rｅｔｕrn ERＲＯＲ；ﻩ｝ﻩwｈile（t！=ｓ、ｔop)ﻩ{priｎtf(” ％d”，*ｔ); /／栈不为空得时候依次输出t＋＋;｝return ERRＯR；｝五、算法及时间复杂度１、算法:建立两个不同类型得空栈,先把一个‘＃’压入运算符栈。

C#算术表达式求值（后缀法），看这⼀篇就够了⼀、种类介绍算术表达式有三种：前缀表达式、中缀表达式和后缀表达式。

⼀般⽤的是中缀，⽐如1+1，前后缀就是把操作符移到前⾯和后⾯，下⾯简单介绍⼀下这三种表达式。

1、前缀表⽰法前缀表⽰法⼜叫波兰表⽰法，他的操作符置于操作数的前⾯（例：+ 1 2），是波兰数学家扬·武卡谢维奇1920年代引⼊的，⽤于简化命题逻辑。

因为我们⼀般认为操作符是在操作数中间的，所以在⽇常⽣活中⽤的不多，但在计算机科学领域占有⼀席之地。

⼀般的表⽰法对计算机来说处理很⿇烦，每个符号都要考虑优先级，还有括号这种会打乱优先级的存在，将使计算机花费⼤量的资源进⾏解析。

⽽前缀表⽰法没有优先级的概念，他是按顺序处理的。

举个例⼦：9-2*3这个式⼦，计算机需要先分析优先级，先乘后减，找到2*3，再进⾏减操作；化成前缀表⽰法就是：- 9 * 2 3，计算机可以依次读取，操作符作⽤于后⼀个操作数，遇到减就是让9减去后⾯的数，⽽跟着9的是乘，也就是说让9减去乘的结果，这对计算机来说很简单，按顺序来就⾏了。

2、中缀表⽰法这也就是我们⼀般的表⽰法，他的操作符置于操作数的中间（例：1 + 2），前⾯也说过这种⽅法不容易被计算机解析，但他符合⼈们的普遍⽤法，许多编程语⾔也就⽤这种⽅法了。

在中缀表⽰法中括号是必须有的，要不然运算顺序会乱掉。

3、后缀表⽰法后缀表⽰法⼜叫逆波兰表⽰法，他的操作符置于操作数的后⾯（例：1 2 +），他和前缀表⽰法都对计算机⽐较友好，但他很容易⽤堆栈解析，所以在计算机中⽤的很多。

他的解释过程⼀般是：操作数⼊栈；遇到操作符时，操作数出栈，求值，将结果⼊栈；当⼀遍后，栈顶就是表达式的值。

因此逆波兰表达式的求值使⽤堆栈结构很容易实现，且能很快求值。

注意：逆波兰记法并不是简单的波兰表达式的反转。

因为对于不满⾜交换律的操作符，它的操作数写法仍然是常规顺序，如，波兰记法/ 6 3的逆波兰记法是6 3 /⽽不是3 6 /；数字的数位写法也是常规顺序。

利用栈来实现算术表达式求值的算法利用栈来实现算术表达式求值的算法算术表达式是指按照一定规则组成的运算式，包含数字、运算符和括号。

在计算机中，求解算术表达式是一项基本的数学运算任务。

根据算术表达式的性质，我们可以考虑利用栈这一数据结构来实现求值算法。

一、算法思路首先，我们需要明确一个重要概念——逆波兰表达式（ReversePolish notation）。

逆波兰表达式是一种没有括号的算术表达式，其运算规则是先计算后面的数字和运算符，再计算前面的数字和运算符。

例如，对于算术表达式“3+4*5-6”，其对应的逆波兰表达式为“3 45 * +6 -”。

那么，我们可以利用栈来实现将中缀表达式转化为逆波兰表达式的过程，具体步骤如下：1. 创建两个栈——操作数栈和操作符栈。

2. 从左到右扫描中缀表达式的每一个数字和运算符，遇到数字则压入操作数栈中，遇到运算符则进行如下操作：（1）如果操作符栈为空或当前运算符的优先级大于栈顶运算符的优先级，则将当前运算符压入操作符栈中。

（2）如果当前运算符的优先级小于或等于栈顶运算符的优先级，则将栈顶运算符弹出并加入操作数栈中，重复此过程直到遇到优先级较低的运算符或操作符栈为空为止，然后将当前运算符压入操作符栈中。

3. 扫描完中缀表达式后，若操作符栈不为空，则将其中所有运算符弹出并加入操作数栈中。

4. 最终，操作数栈中存放的就是逆波兰表达式，我们可以按照逆波兰表达式的计算规则来计算其结果。

二、算法优点利用栈来实现算术表达式求值的算法具有以下优点：1. 代码简洁易懂，易于实现和维护。

2. 由于将中缀表达式转化为逆波兰表达式后，可以减少运算符的优先级关系而消除括号，从而减少求值的复杂度，提高程序的执行效率。

三、代码实现下面是利用栈来实现算术表达式求值的算法的Python代码实现：```pythonclass Stack:def __init__(self):self.items = []def push(self, item):self.items.append(item)def pop(self):return self.items.pop()def peek(self):return self.items[-1]def is_empty(self):return len(self.items) == 0def size(self):return len(self.items)def calculate(op_num1, op_num2, operator):if operator == "+":return op_num1 + op_num2elif operator == "-":return op_num1 - op_num2elif operator == "*":return op_num1 * op_num2elif operator == "/":return op_num1 / op_num2def infix_to_postfix(infix_expr):opstack = Stack()postfix_expr = []prec = {"+": 1, "-": 1, "*": 2, "/": 2, "(": 0} token_list = infix_expr.split()for token in token_list:if token.isdigit():postfix_expr.append(token)elif token == '(':opstack.push(token)elif token == ')':top_token = opstack.pop()while top_token != '(':postfix_expr.append(top_token)top_token = opstack.pop()else:while (not opstack.is_empty()) and(prec[opstack.peek()] >= prec[token]):postfix_expr.append(opstack.pop())opstack.push(token)while not opstack.is_empty():postfix_expr.append(opstack.pop())return " ".join(postfix_expr)def postfix_eval(postfix_expr):opstack = Stack()token_list = postfix_expr.split()for token in token_list:if token.isdigit():opstack.push(int(token))else:op_num2 = opstack.pop()op_num1 = opstack.pop()result = calculate(op_num1, op_num2, token) opstack.push(result)return opstack.pop()infix_expr = "3 + 4 * 5 - 6"postfix_expr = infix_to_postfix(infix_expr)print(postfix_expr)print(postfix_eval(postfix_expr))```四、总结算术表达式求值是一项常见的数学运算任务，利用栈这一数据结构来实现求值算法是一种简单有效的方法，它将中缀表达式转化为逆波兰表达式后，可以消除括号并减少运算符的优先级关系，从而提高程序的执行效率。

数据结构课程设计四则运算表达式求值（C语⾔版）　明⼈不说暗话，直接上，输⼊提取码z3fy即可下载。

⽂件中包含程序，程序运⾏⽂件，设计报告和测试样例，应有尽有，欢迎⼩伙伴们在中下载使⽤。

本课程设计为四则运算表达式求值，⽤于带⼩括号的⼀定范围内正负数的四则运算标准（中缀）表达式的求值。

注意事项：1、请保证输⼊的四则表达式的合法性。

输⼊的中缀表达式中只能含有英⽂符号“+”、“-”、“*”、“/”、“(”、“)”、“=”、数字“0”到“9”以及⼩数点“.”，输⼊“=”表⽰输⼊结束。

例如9+(3-1)*3.567+10/2=，特别是请勿输⼊多余空格和中⽂左右括号。

2、输⼊的中缀表达式默认限定长度是1001，可根据具体情况调整字符串数组的长度。

3、请保证输⼊的操作数在double数据类型范围内，单个数字有效数字长度不可超过15位。

本课程设计中操作数是C语⾔中的双精度浮点数类型。

4、本课程设计中的运算数可以是负数，另外如果是正数可直接省略“+”号（也可带“+”号）。

　下⾯的程序正常运⾏需要在上⾯的百度⽹盘中下载相应⽂件，否则⽆法正常使⽤哦。

1/*本程序为四则运算表达式求值系统，⽤于计算带⼩括号的四则运算表达式求值。

2具体算法：3先将字符串处理成操作单元（操作数或操作符），再利⽤栈根据四则运算4的运算法则进⾏计算，最后得出结果。

*/56 #include<stdio.h>7 #include<ctype.h>8 #include<stdlib.h>9 #include<string.h>10 #include<stdlib.h>11 #include<ctype.h>1213const int Expmax_length = 1001;//表达式最⼤长度，可根据适当情况调整14struct Ope_unit15 {//定义操作单元16int flag;//=1表⽰是操作数 =0表⽰是操作符 -1表⽰符号单元17char oper;//操作符18double real;//操作数，为双精度浮点数19 };2021void Display();//菜单22void Instru(); //使⽤说明23int Check(char Exp_arry[]);24void Evalua(); //先调⽤Conver操作单元化，再调⽤Calculate函数计算结果并输出25int Conver(struct Ope_unit Opeunit_arry[],char Exp_arry[]);//将字符串处理成操作单元26int Isoper(char ch);//判断合法字符（+ - * / ( ) =）27int Ope_Compar(char ope1,char ope2);//操作符运算优先级⽐较28double Calculate(struct Ope_unit Opeunit_arry[],int Opeunit_count,int &flag);//⽤栈计算表达式结果29double Four_arithm(double x,double y,char oper);//四则运算3031int main()32 {33int select;34while(1)35 {36 Display();37 printf("请输⼊欲执⾏功能对应的数字：");38 scanf("%d",&select);39 printf("\n");40switch(select)41 {42case1: Evalua(); break;43case2: Instru(); break;44case0: return0;45default : printf("⽆该数字对应的功能，请重新输⼊\n");46 system("pause");47 }48 }49return0;50 }5152int Check(char Exp_arry[])53 {//检查是否有⾮法字符，返回1表⽰不合法，0表⽰合法54int Explength=strlen(Exp_arry),i;55for(i=0;i<Explength;i++)56 {57if(!Isoper(Exp_arry[i]) && Exp_arry[i] != '.' && !isdigit(Exp_arry[i]))58return1;59if(isdigit(Exp_arry[i]))60 {61int Dig_number=0,Cur_positoin=i+1;62while(isdigit(Exp_arry[Cur_positoin]) || Exp_arry[Cur_positoin]=='.')63 {64 Dig_number++;65 Cur_positoin++;66 }67if(Dig_number >= 16)//最多能够计算15位有效数字68return1;69 }70 }71return0;72 }7374void Evalua()75 {//先调⽤Conver函数将字符串操作单元化，再调⽤Calculate函数计算结果并输出76char Exp_arry[Expmax_length];77int flag=0;//假设刚开始不合法，1表达式合法，0不合法78struct Ope_unit Opeunit_arry[Expmax_length];7980 getchar();//吃掉⼀个换⾏符81 printf("请输⼊四则运算表达式，以=结尾：\n");82 gets(Exp_arry);83 flag=Check(Exp_arry);84if(flag)85 printf("该表达式不合法！\n");86else87 {88int Opeunit_count = Conver(Opeunit_arry,Exp_arry);89double ans = Calculate(Opeunit_arry,Opeunit_count,flag);90if(flag)91 {92 printf("计算结果为：\n");93 printf("%s%lf\n",Exp_arry,ans);94 }95else96 printf("该表达式不合法！\n");97 }98 system("pause");99 }100101int Conver(struct Ope_unit Opeunit_arry[],char Exp_arry[])102 {//将字符串操作单元化103int Explength=strlen(Exp_arry);104int i,Opeunit_count=0;105for(i=0;i<Explength;i++)106 {107if(Isoper(Exp_arry[i]))//是操作符108 {109 Opeunit_arry[Opeunit_count].flag=0;110 Opeunit_arry[Opeunit_count++].oper=Exp_arry[i];111 }112else//是操作数113 {114 Opeunit_arry[Opeunit_count].flag=1;115char temp[Expmax_length];116int k=0;117for(; isdigit(Exp_arry[i]) || Exp_arry[i]=='.' ;i++)118 {119 temp[k++]=Exp_arry[i];120 }121 i--;122 temp[k]='\0';123 Opeunit_arry[Opeunit_count].real=atof(temp);//将字符转化为浮点数124125//负数126if(Opeunit_count == 1 && Opeunit_arry[Opeunit_count-1].flag==0127 && Opeunit_arry[Opeunit_count-1].oper=='-')128 {129 Opeunit_arry[Opeunit_count-1].flag = -1;130 Opeunit_arry[Opeunit_count].real *= -1;131 }// -9132if(Opeunit_count >= 2 && Opeunit_arry[Opeunit_count-1].flag==0133 && Opeunit_arry[Opeunit_count-1].oper=='-' && Opeunit_arry[Opeunit_count-2].flag==0 134 && Opeunit_arry[Opeunit_count-2].oper !=')')135 {136 Opeunit_arry[Opeunit_count-1].flag = -1;137 Opeunit_arry[Opeunit_count].real *= -1;138 }// )-9139140//正数141if(Opeunit_count == 1 && Opeunit_arry[Opeunit_count-1].flag==0142 && Opeunit_arry[Opeunit_count-1].oper=='+')143 {144 Opeunit_arry[Opeunit_count-1].flag = -1;145 }// +9146if(Opeunit_count >= 2 && Opeunit_arry[Opeunit_count-1].flag==0147 && Opeunit_arry[Opeunit_count-1].oper=='+' && Opeunit_arry[Opeunit_count-2].flag==0148 && Opeunit_arry[Opeunit_count-2].oper !=')')149 {150 Opeunit_arry[Opeunit_count-1].flag = -1;151 }// )+9152 Opeunit_count++;153 }154 }155/*for(i=0;i<Opeunit_count;i++)156 {//查看各操作单元是否正确,1是操作数，0是操作符157 if(Opeunit_arry[i].flag == 1)158 printf("该单元是操作数为：%lf\n",Opeunit_arry[i].real);159 else if(Opeunit_arry[i].flag == 0)160 printf("该单元是操作符为：%c\n",Opeunit_arry[i].oper);161 else162 printf("该单元是负号符为：%c\n",Opeunit_arry[i].oper);163 }*/164return Opeunit_count;165 }166167double Calculate(struct Ope_unit Opeunit_arry[],int Opeunit_count,int &flag)168 {//根据运算规则，利⽤栈进⾏计算169int i,dS_pointer=0,oS_pointer=0;//dS_pointer为操作数栈顶指⽰器，oS_pointer为操作符栈顶指⽰器170double Dig_stack[Expmax_length];//操作数栈（顺序存储结构）171char Ope_stack[Expmax_length];//操作符栈172173for(i=0;i<Opeunit_count-1;i++)174 {175if( Opeunit_arry[i].flag != -1 )176 {177if(Opeunit_arry[i].flag)//是操作数178 {179 Dig_stack[dS_pointer++]=Opeunit_arry[i].real;//⼊操作数栈180//printf("%lf\n",Digit[dS_pointer-1]);181 }182else//是操作符 + - * / ( )183 {184//操作符栈为空或者左括号⼊栈185if(oS_pointer==0 || Opeunit_arry[i].oper=='(')186 {187 Ope_stack[oS_pointer++]=Opeunit_arry[i].oper;188//printf("%oS_pointer\Ope_u_count",Operator[oS_pointer-1]);189 }190else191 {192if(Opeunit_arry[i].oper==')')//是右括号将运算符⼀直出栈，直到遇见左括号193 {194 oS_pointer--;//指向栈顶195 dS_pointer--;//指向栈顶196while(Ope_stack[oS_pointer] != '(' && oS_pointer != 0)197 {198 Dig_stack[dS_pointer-1] = Four_arithm(Dig_stack[dS_pointer-1],Dig_stack[dS_pointer], 199 Ope_stack[oS_pointer--]);//oS_pointer--为操作符出栈200201 dS_pointer--;//前⼀个操作数出栈202//printf("操作数栈顶元素等于%lf\n",Digit[dS_pointer]);203 }204 oS_pointer--;//左括号出栈205206 oS_pointer++;//恢复指向栈顶之上207 dS_pointer++;208 }209else if(Ope_Compar(Opeunit_arry[i].oper,Ope_stack[oS_pointer-1]))//和栈顶元素⽐较210 {211 Ope_stack[oS_pointer++]=Opeunit_arry[i].oper;212//printf("%oS_pointer\Ope_u_count",Operator[oS_pointer-1]);213 }214else//运算符出栈，再将该操作符⼊栈215 {216 oS_pointer--;//指向栈顶217 dS_pointer--;//指向栈顶218while(Ope_Compar(Opeunit_arry[i].oper,Ope_stack[oS_pointer])==0 && oS_pointer != -1) 219 {//当前操作符⽐栈顶操作符优先级⾼220 Dig_stack[dS_pointer-1]=Four_arithm(Dig_stack[dS_pointer-1],Dig_stack[dS_pointer], 221 Ope_stack[oS_pointer--]);222 dS_pointer--;223//printf("操作数栈顶元素等于%lf\n",Digit[dS_pointer]);224 }225 oS_pointer++;//恢复指向栈顶之上226 dS_pointer++;227 Ope_stack[oS_pointer++]=Opeunit_arry[i].oper;228 }229 }230 }231 }232 }233/*for(i=0;i<oS_pointer;i++)234 printf("操作符栈%oS_pointer\Ope_u_count",Operator[i]);235 for(i=0;i<dS_pointer;i++)236 printf("操作数栈%lf\n",Digit[i]);*/237 oS_pointer--;//指向栈顶元素238 dS_pointer--;//指向栈顶元素239while(oS_pointer != -1)240 {241 Dig_stack[dS_pointer-1]=Four_arithm(Dig_stack[dS_pointer-1],Dig_stack[dS_pointer], 242 Ope_stack[oS_pointer--]);//oS_pointer--为操作符出栈243 dS_pointer--;//前⼀个操作数出栈244//printf("操作数栈顶元素为%lf\Ope_u_count",Digit[dS_pointer]);245 }246//printf("%dS_pointer,%dS_pointer\n",oS_pointer,dS_pointer);247if(oS_pointer==-1 && dS_pointer==0)248 flag=1;//为1表⽰表达式合法249return Dig_stack[0];250 }251252int Ope_Compar(char ope1,char ope2)253 {//操作符运算优先级⽐较254char list[]={"(+-*/"};255int map[5][5]={//先⾏后列，⾏⽐列的运算级优先级低为0，⾼为1256// ( + - * /257/* ( */1,0,0,0,0,258/* + */1,0,0,0,0,259/* - */1,0,0,0,0,260/* * */1,1,1,0,0,261/* / */1,1,1,0,0 };262int i,j;263for(i=0;i<5;i++)264if(ope1==list[i]) break;265for(j=0;j<5;j++)266if(ope2==list[j]) break;267return map[i][j];268 }269270double Four_arithm(double x,double y,char oper)271 {//四则运算272switch(oper)//保证不含其它运算符273 {274case'+': return x+y;275case'-': return x-y;276case'*': return x*y;277case'/': return x/y;//y不能为0278default : return0;279 }280 }281282int Isoper(char ch)283 {//判断合法字符 + - * / ( ) =284if(ch=='+' || ch=='-' || ch=='*' || ch=='/' || ch=='(' || ch==')' || ch=='=')285return1;286return0;287 }288289void Display()290 {//打印菜单291 system("cls");292 printf("/******************************************************************************/\n");293 printf("\t\t 欢迎使⽤本四则运算表达式求值系统\n");294 printf("\n\t说明：建议请您先阅读使⽤说明，再输⼊相应的数字进⾏操作，谢谢配合！\n"); 295 printf("\n\t\t1 四则运算表达式求值\n");296 printf("\n\t\t2 使⽤说明\n");297 printf("\n\t\t0 退出\n");298 printf("/******************************************************************************/\n");299 }300301void Instru()302 {//打印使⽤说明303 FILE *fp;304char ch;305if( ( fp=fopen("使⽤说明.txt","r") ) == NULL)306 {307 printf("⽂件打开失败！\n");308 exit(0);309 }310for(; (ch = fgetc(fp)) != EOF; )311 putchar(ch);312 fclose(fp);313 printf("\n");314 system("pause");315 }。

表达式求值实验报告西南大学数据结构实验报告学院：专业：班级：姓名：学号：实验报告一、实验题目：表达式表达式二、实验目的和建议：目的：（1）通过该算法的设计思想，熟识栈的特点和应用领域方法；（2）通过对波函数优先法对算术表达式表达式的算法继续执行过程的模拟，认知在继续执行适当栈的操作方式时的变化过程。

（3）通过程序设计，进一步熟识栈的基本运算函数；（4）通过自己动手同时实现算法，强化从伪码算法至c语言程序的同时实现能力。

建议：（1）采用栈的顺序存储则表示方式；（2）采用波函数优先法；（3）用c语言同时实现；（4）从键盘输入一个符合要求的算术表达式，输入恰当的结果。

三、实验过程：#include#include#include#include#include#include#include#include#include#inclu de#include//函数结果状态代码#definetrue1#definefalse0#defineok1#defineerror0#defineinfeasible-1typedefintstatus;//status就是函数的类型,其值就是函数结果状态代码，如ok等typedefintelemtype;constintstack_init_size=100;constintstackincrement=10;typed efstruct{elemtype*base;elemtype*top;intstacksize;}stack;statusinitstack(stack&s){//构造一个空栈ss.base=(elemtype*)malloc(stack_init_size*sizeof(elemtype));if(!s.base)exit(er ror);s.top=s.base;s.stacksize=stack_init_size;returnok;}statuspush(stack&s,ele mtypee){//插入元素e为新的栈顶元素if(s.top-s.base>=s.stacksize){s.base=(elemtype*)realloc(s.base,(s.stacksize+stackincrem ent)*sizeof(elemtype));if(!s.base)exit(overflow);s.top=s.base+s.stacksize;s.st acksize+=stackincrement;}*s.top++=e;returnok;}statuspop(stack&s,elemtype&e){//若栈不空，则删除，用e返回其值，并返回ok；否则返回errorif(s.top==s.base)returnerror;e=*--s.top;returnok;}statusgettop(stack&s){//若栈不空，用e返回s的栈顶元素，并返回ok；否则返回errorif(s.top==s.base)returnerror;return*(s.top-1);}operate.h:#include\statusin(charc){//辨别c与否为运算符if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='#')returnok;elsereturnerror;}statusoper ate(inta,charc,intb){//二元运算switch(c){case'+':returna+b;break;case'-':returna-b;break;case'*':returna*b;break;case'/':if(b==0){printf(\（提示信息：存有除数为零错误）\\n\);returnerror;}//除数无法为零elsereturna/b;break;}}charprecede(chara,charb){//波函数间优先关系switch(a){case'+':switch(b){case'+':return'>';break;case'-':return'>';break;case'*':return'';break;case'#':return'>';break;}break;case'-':switch(b){case'+':return'>';break;case'-':return'>';break;case'*':return'';break;case'#':return'>';break;}break;case'*':switch(b){case'+':return'>';break;case'-':return'>';break;case'*':return'>';break;case'/':return'>';break;case'(':return'';break;case'#':return'>';break;}break;case'/':switch(b){case'+':return'>'; break;case'-':return'>';break;case'*':return'>';break;case'/':return'>';break;case'(':return'';break;case'#':return'>';break;}break;case'(':switch(b){case'+':return'';b reak;case'-':return'>';break;case'*':return'>';break;case'/':return'>';break;case')':return'>';break;case'#':return'>';break;}break;case'#':switch(b)。

逆波兰表达式求值算法逆波兰表示法（Reverse Polish Notation，RPN）是一种数学表达式表示法，它不需要括号来明确操作符的优先级。

在这种表示法中，操作符跟在操作数后面。

下面是一个逆波兰表达式的求值算法：1. 初始化一个堆栈用于存储数字。

2. 从左到右读取表达式中的每个字符。

3. 如果字符是一个数字，则将其转换为对应的数值，并压入堆栈。

4. 如果字符是一个操作符（例如加号、减号、乘号或除号），则从堆栈中弹出两个操作数，进行相应的运算，并将结果压回堆栈。

5. 重复步骤2-4，直到表达式结束。

6. 最后，堆栈中剩下的唯一元素就是表达式的计算结果。

下面是一个使用 Python 实现逆波兰表达式求值算法的示例代码：```pythondef eval_rpn(expression):stack = []operators = set('+-/')for token in ():if token not in operators:(int(token))else:y = ()x = ()if token == '+':(x + y)elif token == '-':(x - y)elif token == '':(x y)else: token == '/'(x // y) 使用整数除法，因为逆波兰表达式通常用于整数运算 return stack[0]```使用示例：```pythonexpression = "2 3 + 4 " 计算 (2 + 3) 4 的结果，即 20 result = eval_rpn(expression)print(result) 输出：20```。

表达式求值，输入一个表达式，如1+2*3#，程序可计算出结果为7支持以下符号：+ - * / ( ) ^ .可以计算整数、小数其中^表示次方，2^5表示2的5次方*//*头文件*/#include <>#include <>#include <>#include <>#include <>/*宏定义*/#define INIT_STACK_SIZE 100#define SET_NUM 8#define N 100/*字符优先级表*/unsigned char prior[SET_NUM][SET_NUM] ={/* '+' '-' '*' '/' '(' ')' '#' '^' *//*'+'*/'>', '>', '<', '<', '<', '>', '>', '<',/*'-'*/'>', '>', '<', '<', '<', '>', '>', '<',/*'*'*/'>', '>', '>', '>', '<', '>', '>', '<',/*'/'*/'>', '>', '>', '>', '<', '>', '>', '<',/*'('*/'<', '<', '<', '<', '<', '=', ' ', '<',/*')'*/'>', '>', '>', '>', ' ', '>', '>', '>',/*'#'*/'<', '<', '<', '<', '<', ' ', '=', '<',/*'^'*/'>', '>', '>', '>', '<', '>', '>', '>'};unsigned char priorSet[SET_NUM] = {'+', '-', '*', '/', '(', ')', '#', '^'};/*结构体定义，这是用来存放字符的栈*/typedef struct{char *base;char *top;int stacksize;} SqStackC;/*结构体定义，这是用来存放数字的栈*/typedef struct{double *base;double *top;int stacksize;} SqStackN;void initStackN(SqStackN &);void initStackC(SqStackC &);void pushN(SqStackN &, double);void pushC(SqStackN &, double);void popN(SqStackN &, double &);void popC(SqStackN &, double &);double calculate(double, char, double);int findInSet(char);char compare(char, char);void getSolution();/*主函数*/void main(){getSolution();}/*初始化数字栈*/void initStackN(SqStackN &S){= (double*) malloc(INIT_STACK_SIZE * sizeof(double));= ;= INIT_STACK_SIZE;}/*初始化字符栈*/void initStackC(SqStackC &S){= (char*) malloc(INIT_STACK_SIZE * sizeof(char));= ;= INIT_STACK_SIZE;}/*向数字栈中存放数字*/void pushN(SqStackN &S, double x){if >=return;*++) = x;}/*向字符栈中存放字符*/void pushC(SqStackC &S, char x){if - >=return;*++) = x;}/*从数字栈中取出数字*/void popN(SqStackN &S, double &x){if ==return;x = *;}/*从字符栈中取出字符*/void popC(SqStackC &S, char &x){if ==return;x = *;}/*这个函数返回a operation b的值。

栈的应⽤——表达式求值 表达式求值是程序设计语⾔编译中的⼀个基本问题，它的实现就是对“栈”的典型应⽤。

本⽂针对表达式求值使⽤的是最简单直观的算法“算符优先法”。

本⽂给出两种⽅式来实现表达式求值，⽅式⼀直接利⽤中缀表达式求值，需要⽤到两个栈，操作数栈和操作符栈。

⾸先置操作数栈为空栈，操作符栈仅有“#”⼀个元素。

依次读⼊表达式中的每个字符，若是操作数则进操作数栈，若是操作符则和操作符栈的栈顶运算符⽐较优先权作相应操作，直⾄整个表达式求值完毕。

⽅式⼆⾸先把中缀表达式转换为后缀表达式并存储起来，然后利⽤读出的后缀表达式完成求值，其本质上是⽅式⼀的分解过程。

表达式求值的代码如下：#include <iostream>#include "stack"#include "map"using namespace std;/* 只能求⼀位整数的加减乘除混合运算 */map<char, pair<int, int>> priority; // 存放各个操作符的栈内栈外优先级,first是栈内,second是栈外char infix[50]; // 存放初始的中缀表达式char postfix[50]; // 存放转化的后缀表达式int result;void MakePriority() // 构造运算符优先级表{priority.insert(make_pair('#', make_pair(0, 0))); // isp(#)=0, icp(#)=0priority.insert(make_pair('\n', make_pair(0, 0))); // isp(\n)=0, icp(\n)=0 表达式结尾的'#'⽤'\n'代替,这样可以省略表达式末尾的结束符'#'priority.insert(make_pair('(', make_pair(1, 6))); // isp(()=1, icp(()=6priority.insert(make_pair('*', make_pair(5, 4))); // isp(*)=5, icp(*)=4priority.insert(make_pair('/', make_pair(5, 4))); // isp(/)=5, icp(/)=4priority.insert(make_pair('%', make_pair(5, 4))); // isp(%)=5, icp(%)=4priority.insert(make_pair('+', make_pair(3, 2))); // isp(+)=3, icp(+)=2priority.insert(make_pair('-', make_pair(3, 2))); // isp(-)=3, icp(-)=2priority.insert(make_pair(')', make_pair(6, 1))); // isp())=6, icp())=1}void InfixToPostfix() // 把中缀表达式转换为后缀表达式{int i = 0;stack<char> optrStack; // 操作符栈char optr; // optr为栈顶的操作符optrStack.push('#');while (!optrStack.empty()){if (isdigit(infix[i])) // 是操作数则直接输出(追加到postfix结尾){postfix[strlen(postfix)] = infix[i];postfix[strlen(postfix) + 1] = '\0';i++; // 读⼊中缀表达式的下⼀个字符}else// 是操作符, ⽐较优先级{optr = optrStack.top(); // 取出栈顶操作符if (priority[infix[i]].second > priority[optr].first) // icp(infix[i]) > isp(optr),infix[i]⼊栈{optrStack.push(infix[i]);i++;}else if (priority[infix[i]].second < priority[optr].first)// icp(infix[i]) < isp(optr),optr退栈并输出{postfix[strlen(postfix)] = optr;postfix[strlen(postfix) + 1] = '\0';optrStack.pop();}else// icp(infix[i]) = isp(optr),退栈但不输出,若退出的是'(',则继续读⼊下⼀个字符{optrStack.pop();if (optr == '(')i++;}}}}void CalculateByPostfix() // 通过后缀表达式求值{int i = 0;stack<int> opndStack; // 操作数栈int left, right; // 左右操作数int value; // 中间结果int newOpnd;while (postfix[i] != '#' && i < strlen(postfix)){switch (postfix[i]){case'+':right = opndStack.top(); // 从操作数栈中取出两个操作数opndStack.pop();left = opndStack.top();opndStack.pop();value = left + right;opndStack.push(value); // 中间结果⼊栈break;case'-':right = opndStack.top();opndStack.pop();left = opndStack.top();opndStack.pop();value = left - right;opndStack.push(value);break;case'*':right = opndStack.top();opndStack.pop();left = opndStack.top();opndStack.pop();value = left * right;opndStack.push(value);break;case'/':right = opndStack.top();opndStack.pop();left = opndStack.top();opndStack.pop();if (right == 0){cerr << "Divide by 0!" << endl;}else{value = left / right;opndStack.push(value);}break;default:newOpnd = (int)(postfix[i] - 48); // 操作数直接⼊栈opndStack.push(newOpnd);break;}i++;}result = opndStack.top();}void CalculateByInfix() // 直接利⽤中缀表达式求值{int i = 0;stack<char> optrStack; // 操作符栈stack<int> opndStack; // 操作数栈char optr; // optr为操作符栈顶的操作符int left, right, value; // 左右操作数以及中间结果optrStack.push('#');optr = optrStack.top();while (!optrStack.empty()) // 直到操作符栈为空{if (isdigit(infix[i])) // 是操作数, 进操作数栈{value = (int)(infix[i] - 48);opndStack.push(value);i++;}else// 是操作符, ⽐较优先级{optr = optrStack.top(); // 取出操作符栈顶的操作符if (priority[infix[i]].second > priority[optr].first) // icp(infix[i]) > isp(optr),infix[i]⼊栈 {optrStack.push(infix[i]);i++;}else if (priority[infix[i]].second < priority[optr].first) // icp(infix[i]) < isp(optr),optr退栈并输出{optrStack.pop();right = opndStack.top(); // 从操作数栈中取出两个操作数opndStack.pop();left = opndStack.top();opndStack.pop();switch (optr){case'+':value = left + right;opndStack.push(value); // 中间结果⼊栈break;case'-':value = left - right;opndStack.push(value); // 中间结果⼊栈break;case'*':value = left * right;opndStack.push(value); // 中间结果⼊栈break;case'/':if (right == 0){cerr << "Divide by 0!" << endl;}else{value = left / right;opndStack.push(value);}break;default:break;}}else{optrStack.pop();if (optr == '(')i++;}}}result = opndStack.top();}int main(){MakePriority(); // 构造运算符优先级表cout << "请输⼊中缀表达式：";cin >> infix;cout << "直接利⽤中缀表达式求值为：";CalculateByInfix();cout << result << endl;cout << "转化为后缀表达式：";InfixToPostfix();for (int i = 0;i < strlen(postfix);i++){cout << postfix[i];}cout << endl;cout << "利⽤后缀表达式求值为：";CalculateByPostfix();cout << result << endl;return0;} 为了⽅便起见，本⽂只是简单的设计了⼀个针对⼀位整数的四则运算进⾏求值的算法，对于处理多位整数的四则运算，需要对本⽂接受输⼊的数据类型进⾏“升阶”，把字符数组换成字符串数组，将⼀个整数的多位数字存⼊⼀个字符串进⾏处理。

表达式求值(数据结构) 表达式求值(数据结构)1.引言1.1 目的1.2 背景1.3 范围2.表达式类型2.1 算术表达式2.1.1 运算符2.1.2 运算数2.2 逻辑表达式2.2.1 逻辑运算符2.2.2 逻辑运算数2.3 字符串表达式2.3.1 字符串连接运算符2.3.2 字符串操作函数3.表达式求值算法3.1 递归下降分析法3.2 栈表达式求值法3.2.1 中缀表达式转后缀表达式3.2.2 后缀表达式求值4.数据结构4.1 操作数栈4.2 运算符栈4.3 后缀表达式栈5.算法实现步骤5.1 输入表达式5.2 初始化栈5.3 处理表达式字符串5.4 根据算法选择相应的方法求值5.5 输出结果6.实例演示6.1 算术表达式求值示例6.2 逻辑表达式求值示例6.3 字符串表达式求值示例7.测试与验证7.1 正常表达式测试7.2 异常表达式测试7.3 性能测试8.总结与展望8.1 本文主要工作8.2 结果评估8.3 存在问题8.4 后续工作附件:附件1、算术表达式求值示例代码附件2、逻辑表达式求值示例代码附件3、字符串表达式求值示例代码法律名词及注释:1.递归下降分析法: 一种基于上下文无关文法进行递归分析的方法，用于处理表达式求值等问题。

2.栈表达式求值法: 使用栈数据结构进行表达式求值的方法。

3.中缀表达式: 常见的数学表达式写法，运算符位于运算数之间。

4.后缀表达式: 也称为逆波兰表达式，运算符位于运算数之后。

5.操作数栈: 用于存储表达式中的操作数的栈。

6.运算符栈: 用于存储表达式中的运算符的栈。

7.后缀表达式栈: 用于存储后缀表达式的栈。

表达式求值（⽆括号）对于⾃然数的表达式求值，操作有加、减、乘、除和幂运算，分别⽤+，-， *， /，^来表⽰，为⽅便运算，加⼊#运算符，其运算优先级最低，由于运算符优先级不⼀样，可以利⽤栈实现此操作。

算法思想（1）规定运算符的优先级表（2）设置两个栈：OVS(运算数栈)和OPTR（运算符栈），为了操作⽅便可以先在OPTR栈中先放⼀个#运算符（3）⾃左向右扫描，进⾏如下处理：若遇到运算数则⾦OVS栈；若遇到运算符则与OPTR栈顶运算符进⾏⽐较：•如果当前运算符的优先级⼤于OPTR栈顶运算符的优先级，则当前运算符进⼊OPTR栈；•如果当前运算符的优先级⼤于等于OPTR栈顶运算符的优先级，则OPTR退栈⼀次，得到栈顶运算符op，连续退栈OVS两次，得到运算数a 和b，执⾏op运算，得到结果T，将T进OVS栈。

可以⾃⼰画⼀个表达式两个栈的变化图，有助于理解#include<stdio.h>#include<stdlib.h>#include<math.h>#include<stdbool.h>typedef struct node{int data;//⽆论对于运算符还是运算数，都⽤int型变量来保存node *next;}LinkStackNode, *LinkStack;void InitStack(LinkStack *S){//初始化链栈*S = (LinkStack)malloc(sizeof(LinkStackNode));(*S)->next = NULL;}int Push(LinkStack top, int x){// 进栈操作LinkStackNode *temp;temp = (LinkStackNode*)malloc(sizeof(LinkStackNode));if(temp == NULL) return0;temp->data = x;temp->next = top->next;top->next = temp;return1;}int Pop(LinkStack top, int *x){//出栈操作LinkStackNode *temp;temp = top->next;if(temp == NULL) return0;*x = temp->data;top->next = temp->next;free(temp);return1;}int GetNum(char ch){//返回字符对应的数字return ch - '0';}bool IsEmpty(LinkStack top){//栈为空返回假if(top->next == NULL) return false;return true;}int GetTop(LinkStack top){//返回栈顶元素if(top->next == NULL) return1;return top->next->data;}char Compare(char ch1, char ch2){//实现运算符优先级⽐较switch(ch1){case'#':switch(ch2){case'#': return'=';case'+':case'-':case'*':case'/':case'^': return'<';}case'+':switch(ch2){case'#': return'>';case'+':case'-': return'=';case'*':case'/':case'^': return'<';}case'-':switch(ch2){case'#': return'>';case'+':case'-': return'=';case'*':case'/':case'^': return'<';}case'*':switch(ch2){case'#':case'+':case'-': return'>';case'*':case'/': return'=';case'^': return'<';}case'/':switch(ch2){case'#':case'+':case'-': return'>';case'*':case'/': return'=';case'^': return'<';}case'^':switch(ch2){case'#':case'+':case'-':case'*':case'/': return'>';case'^': return'=';}}}int Calculate(int a, char op, int b){//计算 a op b 的值int c;switch(op){case'-': c = a - b; break;case'+': c = a + b; break;case'*': c = a * b; break;case'/': c = a / b; break;case'^': c = pow(a, b); break;default : c = 0;}return c;}int ExpEvaluation(){//实现LinkStack ovs, optr;InitStack(&ovs);InitStack(&optr);Push(optr, (int)'#');printf("\n\nPlease input an expression(Ending with '#'):\n");char ch = getchar();int num = 0, a, b, t, op, zan;while(ch != '#' || (char)GetTop(optr) != '#'){while(ch >= '0' && ch <= '9'){//如果数字不是⼀位数字，便把字符转化为数字 num = num * 10 + GetNum(ch);ch = getchar();}if(num != 0){//如果num不为0便进OVS栈Push(ovs, num);num = 0;//把num置零}else{switch(Compare(ch, (char)GetTop(optr))){//对运算符优先级进⾏⽐较，实现对应三种关系的操作case'>': Push(optr, (int)ch); ch = getchar(); break;case'=':case'<': Pop(optr, &op);Pop(ovs, &a);Pop(ovs, &b);t = Calculate(b, (char)op, a);Push(ovs, t);break;}}}t = GetTop(ovs);//取栈顶元素，返回值return t;}int main(){int ans = ExpEvaluation();printf("%d\n", ans);return0;}。

150.波兰表达式求值根据，求表达式的值。

有效的运算符包括 +, -, *, / 。

每个运算对象可以是整数，也可以是另⼀个逆波兰表达式。

说明：*整数除法只保留整数部分。

*给定逆波兰表达式总是有效的。

换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

⽰例 1：输⼊: ["2", "1", "+", "3", "*"]输出: 9解释: ((2 + 1) * 3) = 9⽰例 2：输⼊: ["4", "13", "5", "/", "+"]输出: 6解释: (4 + (13 / 5)) = 6⽰例 3：输⼊: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]输出: 22解释:((10 * (6 / ((9 + 3) * -11))) + 17) + 5= ((10 * (6 / (12 * -11))) + 17) + 5= ((10 * (6 / -132)) + 17) + 5= ((10 * 0) + 17) + 5= (0 + 17) + 5= 17 + 5= 22栈⽅式实现from typing import Listclass Solution:def evalRPN(self, tokens: List[str]) -> int:stack = []op = {'+', '-', '*', '/'}for i in tokens:if i in op:tmp = 0# 此处跌倒，刚开始直接tmp = stack.pop() - stack.pop()，这样导致前后运算值交换，减法和除法出错right = stack.pop()left = stack.pop()if i == '+':tmp = left + rightelif i == '-':tmp = left - rightelif i == '*':tmp = left * rightelse:tmp = left / right # 此处遇坑，使⽤了整除运算//stack.append(int(tmp))else:stack.append(int(i))return stack[0]。

数据结构（C语言版）课程设计报告表达式求值说明书XX大学数据结构课程设计说明书题目:表达式求值院系：计算机科学与工程学院专业班级：计算机班学号：学生姓名：指导教师：2021年X月X日XX大学课程设计（论文）任务书计算机科学与工程学院学号学生姓名专业（班级）设计题目表达式求值设计技术参数系统平台：Windows7/WindowsXP开发工具：VC++6.0设计要求（1）能够计算的运算符包括：加、减、乘、除、圆括号。

（2）能够计算的数要求在实数范围内。

（3）能执行多重括号嵌套运算。

（4）对于异常表达式给出错误提示。

工作量课程设计报告要求不少于3000字。

源程序要求不少于300行工作计划2021.11.21-12.01根据课程设计大纲的要求，查找相关资料，完成需求分析；2021.12.02-12.16进行系统的概要设计；2021.12.17-12.31进行系统的详细设计和源代码的书写；2021.01.01-01.17对系统进行调试分析，写出课程设计报告。

参考资料[1]何钦铭主编.C语言程序设计.北京：高等教育出版社,2021.[2]谭浩强编著.C程序设计（第四版）.北京：清华大学出版社,2021.[3]严蔚敏,吴伟民编著.数据结构（C语言版）北京：清华大学出版社,2021.[4]严蔚敏,吴伟民编著.数据结构题集北京：清华大学出版社,2021.指导教师签字教研室主任签字2021年X月X日学生姓名：学号：专业班级：课程设计题目：表达式求值指导教师评语：成绩：指导教师：年月日XX大学课程设计（论文）成绩评定表目录1需求分析12概要设计12.1设计思路12.2存储结构设计12.3功能模块设计13详细设计14运行与测试15总结1参考文献2(要求：给出一级目录和二级目录，宋体，四号字,1.5倍行距，页码使用罗马数字，居中)（报告正文部分）：(要求：正文部分一律用小四号字，宋体，行距20磅。

一级标题靠左，加粗。

二级大标题靠左，不加粗。

表达式求值(数据结构)表达式求值(数据结构)一、引言表达式求值是计算机科学中一个重要的概念，它是计算机程序中常见的操作之一。

通过对表达式中的运算符和操作数进行计算，可以得到表达式的结果。

本文将介绍表达式求值的相关知识和算法，并提供一个基于数据结构的表达式求值的范本。

二、基本概念1.表达式：由操作数、运算符和括号组成的符号串，用于表示一个计算过程。

2.操作数：表达式中用于参与计算的数值或变量。

3.运算符：表达式中用于进行运算的符号，如加减乘除等。

4.括号：用于控制运算优先级和改变运算次序的符号。

三、表达式求值的算法表达式求值的基本思路是通过遍历表达式字符串并利用栈来进行计算。

1.建立一个操作数栈和一个运算符栈。

2.从左到右遍历表达式字符串，依次处理每个字符。

3.如果当前字符是操作数，则直接入操作数栈。

4.如果当前字符是运算符，则进行如下处理：●如果运算符栈为空或栈顶运算符是左括号，则将当前运算符入运算符栈。

●如果当前运算符的优先级高于栈顶运算符的优先级，则将当前运算符入运算符栈。

●如果当前运算符的优先级低于或等于栈顶运算符的优先级，则从运算符栈顶取出一个运算符进行计算，并将结果入操作数栈，直到栈顶运算符的优先级低于当前运算符，然后将当前运算符入运算符栈。

5.如果当前字符是左括号，则将其入运算符栈。

6.如果当前字符是右括号，则从运算符栈顶取出一个运算符进行计算，并将结果入操作数栈，直到取出的运算符是左括号。

7.遍历完表达式字符串后，将运算符栈中剩余的运算符依次取出进行计算，并将结果入操作数栈。

8.操作数栈中最后剩下的元素即为表达式的求值结果。

四、示例代码```pythonclass ExpressionEvaluation:def __init__(self, expression):self.expression = expressionself.operators = []self.operands = []self.precedence = {'+': 1, '.': 1, '': 2, '/': 2}def evaluate(self):for char in self.expression:if char.isdigit():self.operands.append(int(char))elif char in self.precedence:while self.operators andself.operators[.1] != '(' and self.precedence[char] <= self.precedence[self.operators[.1]]:lculate()self.operators.append(char)elif char == '(':self.operators.append(char)elif char == ')':while self.operators[.1] != '(':lculate()self.operators.pop()while self.operators:lculate()return self.operands[.1]def calculate(self):operator = self.operators.pop()operand2 = self.operands.pop()operand1 = self.operands.pop()if operator == '+':self.operands.append(operand1 + operand2)elif operator == '.':self.operands.append(operand1 ●operand2) elif operator == '':self.operands.append(operand1 operand2) elif operator == '/':self.operands.append(operand1 / operand2) expression = \。

算术中缀表达式求值（简单计算器的运算）1. 转化中缀表达式直接求值实现并不现实，需要转化成后缀表达式才能求值。

1. 过程2. 开两个栈，⼀个为符号栈，⼀个为数字栈，分别执⾏不同的分⽀操作。

*当遇到左括号时⽴刻将其压⼈栈中，直到遇到右括号时将左右括号之间的符号和数字全部弹出运算。

*遇到⼀个数字时，将数字压⼊数字栈中。

*遇到⼀个运算符时，将运算符与栈顶运算符⽐较，有下列四种情况：1. 如果当前运算符⽐栈顶运算符优先级要⾼，或者为左括号后的第⼀个运算符，则将其压⼊栈中。

2. 如果它⽐栈中元素优先级低或⼩，则弹出栈顶运算符并运算。

3. 继续⽐较，如果他⽐新的栈顶运算符优先级⾼，则回到第⼀步，否则重复2,3步。

4. 如果扫描到了中缀表达式的末尾，则弹出所有运算符和相应位置的数字进⾏运算。

（如果碰到两位数，⽤标记数组先记录下来，再在计算中转化）3.代码展⽰（code.Js）1.两步分别为操作栈和运算#include<iostream>#include<stack>#include<cstring>#include<iomanip>using namespace std;char endnumber[100];//数字和字符栈char number[100];//两位数特殊下标int z = 0;//下标//a,b优先级⽐较bool cmp(char a,char b){if(a == '*'||a == '/'){if(b == '*'||b == '/'){return false;}else{return true;}}else{return false;}}//使⽤过渡栈存⼊后缀表达式void get_stack(string s){memset(number,1,sizeof(number));stack<char>attitude;int l = s.length();int i = 0;for(i = 0;i < l;i++){char t = s[i];if(t == '('){attitude.push(t);}else if(t == ')'){char str1 = attitude.top();while(str1 != '('){endnumber[z++] = str1;attitude.pop();str1 = attitude.top();attitude.pop();}else if(t >= '0'&&t <= '9'){if(s[i+1] >= '0'&&s[i+1] <= '9'){number[z] = '0';endnumber[z] = s[i];z++;endnumber[z] = s[i+1];z++;i++;}else{endnumber[z++] = s[i];}}else{if(attitude.empty()){attitude.push(t);}else{char str2 = attitude.top();if(cmp(t,str2) || str2 == '('){attitude.push(t);}else{while(!cmp(t,str2)&&str2 != '('&&!attitude.empty()){attitude.pop();endnumber[z++] = str2;if(!attitude.empty())str2 = attitude.top();}attitude.push(t);}}}}while(!attitude.empty()){char str3 = attitude.top();endnumber[z++] = str3;attitude.pop();}// for(i = 0;i < z;i++)// cout<<endnumber[i]<<" ";}//从存储中调出数字和字符进⾏计算,转换成浮点数计算精确值void get_calculate(string s){int k = 1;stack<float>put_stack;if(number[0] == '0'){put_stack.push(((endnumber[0] - '0')*10+(endnumber[1]-'0'))*1.0);k++;}elseput_stack.push(1.0*(endnumber[0] - '0'));for(int i = k;i < z;i++){char t = endnumber[i];if(t >= '0'&&t <= '9'){if(number[i] == '0'){put_stack.push(((endnumber[i] - '0')*10+(endnumber[i+1]-'0'))*1.0); i++;}else{put_stack.push((t - '0')*1.0);}}elsefloat x = put_stack.top();put_stack.pop();float y = put_stack.top();put_stack.pop();float tmp;if(t == '+')tmp = x+y;else if(t == '-')tmp = y-x;else if(t == '*')tmp = x*y;elsetmp = y/x;put_stack.push(tmp);}}cout<<setiosflags(ios::fixed)<<setprecision(2)<<put_stack.top(); }int main(){string exp_middle;//中缀表达式cin>>exp_middle;get_stack(exp_middle);get_calculate(exp_middle);return0;}。