利用栈实现表达式求解课件

一、程序设计任务掌握栈的用法，实现表达式求值这一栈的典型应用问题：以字符序列的形式从终端输入语法正确的、不含变量的算术表达式，利用算符优先关系，实现对算术四则混合运算表达式求值。

当用户输入一个合法的表达式后，能够返回正确的结果。

能够计算的运算符包括：加、减、乘、除、括号。

二、具体代码实现如下#include<iostream.h>#include<fstream.h>#include<string.h>#include<stdlib.h>#include<math.h>#include<cstdio> //cstdio本来就只是将stdio.h的内容用C++的头文件形式表现出来。

#define NULL 0typedef struct node //定义一个结点结构体{char date;struct node *next;}SNode;SNode *InitStack()//初始化空链栈{SNode *top;top=new SNode;//top=(SNode *)malloc(sizeof(SNode));top->next=NULL;return top;}void PushOptr(SNode *top,char x)//运算符进栈函数{SNode *p;p=new SNode;p->date=x;p->next=top->next;top->next=p;}char PopOptr(SNode *top)//运算符出栈函数{SNode *p;char x;if(top==NULL)return NULL;p=top->next;x=p->date;top->next=p->next;delete p;return x;}void PushOpnd(SNode *top,char x)//操作数进栈函数{SNode *p;p=new SNode;p->date=x;p->next=top->next;top->next=p;}char PopOpnd(SNode *top)//操作数出栈函数{SNode *p;char x;if(top==NULL)return NULL;p=top->next;x=p->date;top->next=p->next;delete p;return x;}char GetTop(SNode *top)//取栈顶元素{return (top->next)->date;}int In(char c){int n;switch(c){case '+':case '-':case '*':case '/':case '(':case ')':case '%':case '^':case '#': n=1;break;default : n=0;break;}return n;}char Precede(char x,char y) //符号优先级规则说明{int i,j;int form[9][9]={{1,1,-1,-1,-1,1,-1,-1,1},{1,1,-1,-1,-1,1,-1,-1,1},{1,1,1,1,-1,1,1,-1,1},{1,1,1,1,-1,1,1,-1,1},{-1,-1,-1,-1,-1,0,-1,-1,2},{1,1,1,1,2,1,1,1,1},{1,1,1,1,-1,1,1,-1,1},{1,1,1,1,-1,1,1,1,1},{-1,-1,-1,-1,-1,2,-1,-1,0}}; //定义一个二维数组存放运算符优先级switch(x){case '+':i=0;break;case '-':i=1;break;case '*':i=2;break;case '/':i=3;break;case '(':i=4;break;case ')':i=5;break;case '%':i=6;break;case '^':i=7;break;case '#':i=8;break;}switch(y){case '+':j=0;break;case '-':j=1;break;case '*':j=2;break;case '/':j=3;break;case '(':j=4;break;case ')':j=5;break;case '%':j=6;break;case '^':j=7;break;case '#':j=8;break;}if(form[i][j]==1) //当form[i][j]==1时，说明运算符i的优先级高于运算符jreturn '>';elseif(form[i][j]==-1) //当form[i][j]==-1时，说明运算符i的优先级低于运算符jreturn '<';else //当form[i][j]等于其他值时，说明运算符i的优先级等于运算符jreturn '=';}int Operate(char x,char z,char y)//操作函数{int a=x-'0',b=y-'0';switch(z){case '+':return a+b;case '-':return a-b;case '*':return a*b;case '/':return a/b;case '%':return a%b;case '^': for(int i=1;i<b;i++) a*=a; return a;// cout<<pow(a,b);}}char Eval_Exp(char t[]) //获取运算结果{char temp[30];strcpy(temp,t);strcat(temp,"#");char a,b,c,r,f,z;int result,i=0;SNode *top[2];top[0]=InitStack(); //top[0]指向栈顶PushOptr(top[0],'#'); //将‘#’进入空运算符栈top[1]=InitStack();c=temp[i];while(c!='#'||(GetTop(top[0]))!='#')//输入符号不为‘#’或者栈顶元素不为‘#’时执行while语句{if(!In(c)) //如果当前输入不为运算符时执行if语句{PushOpnd(top[1],c); //将输入的元素放入操作数栈中c=temp[++i];}else{r=Precede(GetTop(top[0]),c); //获取符号优先级比较结果switch(r){case '<':PushOptr(top[0],c); //将当前输入的运算符进运算符栈中c=temp[++i];break;case '=':PopOptr(top[0]); //出当前运算符栈中的栈顶元素c=temp[++i];break;case '>':b=PopOptr(top[0]); //出当前运算符栈中的栈顶元素a=PopOpnd(top[1]); //出当前操作数栈中栈顶元素z=PopOpnd(top[1]); //出当前操作数栈中栈顶元素result=Operate(z,b,a); //计算结果f=result+'0';PushOpnd(top[1],f); //将运算结果进操作数栈中break;}}}return f; //返回运算结果}void main(){char infilename[40],outfilename[40],ch[30];fstream infile;fstream outfile;cout<<"请输入操作文件名路径: ";cin>>infilename;infile.open(infilename,ios::in|ios::nocreate);if(!infile){cout<<"不能打开文件："<<infilename<<endl;exit(1);}cout<<"请输入结果文件名路径: ";cin>>outfilename;outfile.open(outfilename,ios::out);if(!outfile){cout<<"不能打开文件："<<outfilename<<endl;exit(2);}while(infile.getline(ch,80))outfile<<Eval_Exp(ch)-'0'<<endl;infile.close();outfile.close();}三、运行输出结果实例输入表达式实例：2+5*（6-2）/2运行结果如下：。

数据结构学习（C++）—栈应用（表达式求值）happycock（原作）转自CSDN栈的应用很广泛，原书只讲解了表达式求值，那我也就只写这些。

其实，栈的最大的用途是解决回溯问题，这也包含了消解递归；而当你用栈解决回溯问题成了习惯的时候，你就很少想到用递归了，比如迷宫求解。

另外，人的习惯也是先入为主的，比如树的遍历，从学的那天开始，就是递归算法，虽然书上也教了用栈实现的方法，但应用的时候，你首先想到的还是递归；当然了，如果语言本身不支持递归（如BASIC），那栈就是唯一的选择了——好像现在的高级语言都是支持递归的。

如下是表达式类的定义和实现，表达式可以是中缀表示也可以是后缀表示，用头节点数据域里的type区分，这里有一点说明的是，由于单链表的赋值函数，我原来写的时候没有复制头节点的内容，所以，要是在两个表达式之间赋值，头节点里存的信息就丢了。

你可以改写单链表的赋值函数来解决这个隐患，或者你根本不不在两个表达式之间赋值也行。

#ifndef Expression_H#define Expression_H#include "List.h"#include "Stack.h"#define INFIX 0#define POSTFIX 1#define OPND 4#define OPTR 8template <class Type> class ExpNode{public:int type;union { Type opnd; char optr;};ExpNode() : type(INFIX), optr('=') {}ExpNode(Type opnd) : type(OPND), opnd(opnd) {}ExpNode(char optr) : type(OPTR), optr(optr) {}};template <class Type> class Expression : List<ExpNode<Type> >{public:void Input(){MakeEmpty(); Get()->type =INFIX;cout << endl << "输入表达式，以＝结束输入" << endl;Type opnd; char optr = ' ';while (optr != '='){cin >> opnd;if (opnd != 0){ExpNode<Type> newopnd(opnd);LastInsert(newopnd);}cin >> optr;ExpNode<Type> newoptr(optr);LastInsert(newoptr);}}。

栈实现表达式计算【数据结构】思路：所包含的运算符有‘+’，‘-’，‘*’，‘/’，‘（’，‘）’。

（1）建⽴两个栈，⼀个⽤来存储操作数，另⼀个⽤来存储运算符, 开始时在运算符栈中先压⼊‘/0’，⼀个表达式的结束符。

（2）然后从左⾄右依次读取表达式中的各个符号（操作数或者运算符）；（3）如果读到的是操作数直接存⼊操作数栈；（4）如果读到的是运算符，则作进⼀步判断：若读到的是‘/0’结束符，⽽且此时运算符栈的栈顶元素也是‘/0’结束符，则运算结束，输出操作数栈中的元素即为最后结果。

若读到的是‘（’或者读到的运算符的优先级⽐⽬前的运算符栈中的栈顶元素的优先级⾼，则将运算符直接存⼊运算符栈，继续读表达式中的下⼀个符号，重复步骤（3）和（4）；若读到的是‘)’,⽽且此时运算符栈的栈顶元素是‘(’结束符，则将运算符栈中的栈顶元素退出来，继续读表达式中的下⼀个符号，重复步骤（3）和（4）；若读到的运算符的优先级等于或⼩于之前的运算符的优先级，则从操作数中退出2个，从运算符中退出⼀个进⾏运算，将运算结果存⼊操作数栈；再把之前读到的运算符与⽬前的运算符栈顶⽐较，重复步骤（4）（即现在不读下⼀个元素）；#include <iostream>#include <stack>using namespace std;double toNum(char*s, int &k){int flag = 0;double x = 0.0, y = 0.1;while (s[k] >= '0'&&s[k] <= '9' || s[k] == '.'){if (s[k] >= '0'&&s[k] <= '9'){if (flag == 0)x = x * 10 + s[k] - '0';else{x = x + y*(s[k] - '0');y = y*0.1;}}else{flag = 1;}k = k + 1;}return x;}int priority(char c){int k;switch (c){case '*':k = 2; break;case '/':k = 2; break;case '+':k = 1; break;case '-':k = 1; break;case '(':k = 0; break;case ')':k = 0; break;default:k = -1; break;}return k;}int main(){stack<double> sv;stack<char> sp;char c;int k = 0, flag = 1;double x, y;sp.push('\0');char *s = new char[100];cout << "请输⼊算式：" << endl;cin >> s;c = s[k];while (flag){if (c >= '0'&&c <= '9' || c == '.'){sv.push(toNum(s, k));}else if (c == '\0'&& sp.top() == '\0'){flag = 0;}else if (c == '(' || (priority(c) > priority(sp.top()))) {sp.push(c);k++;}else if (c == ')'&& sp.top() == '('){sp.pop();k++;}else if (priority(c) <= priority(sp.top())){x = sv.top();sv.pop();y = sv.top();sv.pop();c = sp.top();sp.pop();switch (c){case '+':y = x + y; break;case '-':y = y - x; break;case '*':y = x*y; break;case '/':y = y / x; break;}sv.push(y);}c = s[k];}cout << sv.top() << endl;return 0;}。

利用栈实现表达式求值c语言要实现表达式求值，我们可以使用一个数据结构来保存操作的优先级和操作数。

在这个例子中，我们将使用栈。

下面是一个使用C语言实现的基本例子：```cinclude <>include <>include <>include <>define MAX_STACK_SIZE 100typedef enum {NUMBER,PLUS,MINUS,MUL,DIV} Token;typedef struct Stack {Token data[MAX_STACK_SIZE];int top;} Stack;void push(Stack stack, Token data) {if (stack->top == MAX_STACK_SIZE - 1) {printf("Stack is full\n");return;}stack->top++;stack->data[stack->top] = data;}Token pop(Stack stack) {if (stack->top == -1) {printf("Stack is empty\n");return NUMBER; // return some default value when stack is empty}Token data = stack->data[stack->top];stack->top--;return data;}bool isOperator(Token token) {return token == PLUS token == MINUS token == MUL token == DIV;}bool isLeftAssociative(Token token) {return token == PLUS token == MINUS;}bool isRightAssociative(Token token) {return token == MUL token == DIV;}Token getPriority(Token token) {if (token == PLUS token == MINUS) return 1; // + and - have higher priority than and /if (token == MUL token == DIV) return 2; // and / have higher priority than + and -return 0; // if token is not an operator, return 0 as default value }bool isOperatorPriorityHigher(Token op1, Token op2) {return getPriority(op1) > getPriority(op2); // higher priority means higher value of getPriority() function result}bool isOperatorPrioritySame(Token op1, Token op2) {return getPriority(op1) == getPriority(op2); // same priority means getPriority() function result is equal for both operators}void evaluateExpression() {Stack stack; // create a stack to store tokens (numbers and operators) in reverse order of their appearance in the expression string= -1; // initialize stack top to -1 to indicate an empty stackchar expression[] = "3+52"; // example expression stringchar token = strtok(expression, " "); // tokenize the expression stringwhile (token != NULL) {if (isdigit(token[0])) { // if token is a number, push it to the stack push(&stack, NUMBER); // push the number to the stackpush(&stack, (Token)(atoi(token))); // convert the string to an integer and push it to the stack} else if (isOperator(atoi(token))) { // if token is an operator, push it to the stackpush(&stack, (Token)(atoi(token))); // convert the string to an operator and push it to the stack}token = strtok(NULL, " "); // continue tokenizing the expression string}while ( != -1) {Token data = pop(&stack); // pop the topmost element from the stackif (isOperator(data)) { // if popped element is an operator, apply it to the top two elements of the stackToken op2 = pop(&stack); // pop the topmost element from the stackToken op1 = pop(&stack); // pop the next topmost element from the stackif (isLeftAssociative(data)) { // apply left associative operator push(&stack, op1); // push the operand on which the operator is applied first to the stackpush(&stack, op2); // push the second operand to the stackpush(&stack, data); // push the operator to the stack。

栈的应⽤—算术表达式求值例三、算术表达式求值1、问题描述当⼀个算术表达式中含有多个运算符，且运算符的优先级不同的情况下，如何才能处理⼀个算术表达式2、思路⾸先我们要知道表达式分为三类：①中缀表达式：a+(b-c/d)*e②前缀表达式+a*-be③后缀表达式abcd/-e*+由于运算符有优先级，所以在计算机中计算⼀个中缀的表达式⾮常困难，特别是带括号的更⿇烦，⽽后缀表达式中既⽆运算符优先⼜⽆括号的约束问题因为在后缀表达式中运算符出现的顺序正是计算的顺序，所以计算⼀个后缀的表达式更简单。

所以，可以将求算术表达式的值的过程化成两个过程：1.将⼀个中缀表达式化成⼀个后缀表达式2.对后缀表达式进⾏求值⼀、将中缀变成⼀个后缀因为要将运算符出现的次序与真正的算术运算顺序⼀直，所以，就要让优先级⾼的以及括号内的运算符出现在前⾯，因此要使⽤⼀个栈来保留还未送往后缀表达式的运算符，此栈称为运算符栈算法描述如下：（1）初始化⼀个运算符栈（2）从算术表达式输⼊的字符串中，从左到右的读取⼀个字符（3）若当前的字符是操作数，则直接送往后缀表达式（4）若当前的字符是左括号，则将其压⼊运算符栈（5）若当前的字符是操作符，则进⾏如下操作：①当运算符栈为空时，直接将其压⼊栈。

②当此运算符的优先级⾼于栈顶的运算符时，则将此运算符压⼊栈，否则，弹出栈顶运算符送往后缀式，并将当前运算符压栈，重复步骤（5）（6）若当前字符是右括号，反复将栈顶符号弹出，并送往后缀表达式中，知道栈顶元素为左括号为⽌，然后将左括号出栈并丢弃（7）若读取还未结束，则重复步骤（2）（8）若读取结束，则将栈中剩余的所有的运算符弹出并送往后缀表达式⼆、计算后缀表达式的值计算步骤很简单，就是找到运算符，然后找前⾯最后出现的两个操作数，从⽽构成⼀个最⼩的算术表达式进⾏运算，在计算过程中也需要利⽤⼀个栈来保留后缀表达式中还未参与运算的操作数，称为操作数栈，算法描述如下：（1）初始化⼀个操作数栈（2）从左到右依次读⼊后缀表达式中的字符①若当前字符是操作数，则压⼊操作数栈。

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

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

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

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

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

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

表达式求值的代码如下：#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;} 为了⽅便起见，本⽂只是简单的设计了⼀个针对⼀位整数的四则运算进⾏求值的算法，对于处理多位整数的四则运算，需要对本⽂接受输⼊的数据类型进⾏“升阶”，把字符数组换成字符串数组，将⼀个整数的多位数字存⼊⼀个字符串进⾏处理。