②表达式求值
表达式求值是程序设计语言编译中的一个最基本的问题。我们讨论一种简单直观的方法“算法优先级法”
算术四则运算的规则：
1、从左到右
2、先乘除后加减
3、先括号内，后括号外
【例】4 + 2*3 -10/5 每一步的计算顺序应该是：
4 + 2*3 -10/5 = 4 + 6 - 10/5 = 10 - 10/5 = 10 - 2 = 8
算法步骤：（我们假设表达式以字符‘#’结尾）
（1）首先，创建空运算符栈OPTR，将表达式起始符‘#’压入栈底，创建空操作数栈OPND
（2）依次读入表达式中的每个字符，若是操作数则进操作数栈，若是运算符则和运算符栈顶的运算符比较优先级后，做如下相应操作：
1.如果栈顶的运算符优先级较低，则把新的运算符压入OPTR；执行（2）
2.如果栈顶的运算符优先级较高，则将其 和 操作数栈的两个栈顶元素 退栈，计算3个元素组成的表达式的值，再压入操作数栈，然后继续判断；
3.如果栈顶的运算符优先级相等（除了#符外，只有‘(’和‘)’是相等的），则将‘（’出栈；执行（2）
（3）直到整个表达式求值完毕（即OPTR栈顶元素和当前读入的字符均为‘#’）
具体算法实现：
#include <iostream> #include <stack>//C++中使用栈要包含的头文件 using namespace std; //符号数组 char symbol[7] = {'+', '-', '*', '/', '(', ')', '#'}; //栈内元素的优先级 int in[7] = {3, 3, 5, 5, 1, 6, 0}; //栈外元素的优先级 int out[7] = {2, 2, 4, 4, 6, 1, 0}; /* * 通过符号字符获取它的数组下标 */ int get(char c) { switch(c) { case '+': return 0; case '-': return 1; case '*': return 2; case '/': return 3; case '(': return 4; case ')': return 5; case '#': return 6; default: return 6; } } /* * 比较栈内运算符c1和栈外运算符c2的优先级 */ char precede(char c1, char c2) { int i1 = get(c1); int i2 = get(c2); if(in[i1] > out[i2]) { return '>'; } else if(in[i1] < out[i2]) { return '<'; } else { return '='; } } /* * 计算基本表达式的值 */ int figure(int a, int theta, int b) { switch(theta) { case 0: return a + b; case 1: return a - b; case 2: return a * b; default: return a / b; } } /* * 计算表达式的值 */ int EvaluateExpression(const char *exp) { stack<int> OPND; //操作数栈 stack<int> OPTR; //运算符栈 OPTR.push(get('#')); int flag = 1; //表示正负号 1,表示正 0,表示负 int a, theta, b; if(!('+' == *exp || '-' == *exp || '(' == *exp || isdigit(*exp))) {//如果不是以'+'、'-'、'('或者数字的其中一个开头，则表达式错误 cout << "表达式出错1" << endl; return -1; } if('+' == *exp) { exp++;//指向下一个字符 } else if('-' == *exp) { flag = 0; exp++;//指向下一个字符 } int index = OPTR.top(); //获取运算符栈顶元素在数组的下标号 while(*exp || symbol[index] != '#') //如果栈顶元素是'#'且当前元素为空结束计算 { if(isdigit(*exp)) {//如果当前元素是数字，计算整个操作数的值，然后压入操作数栈 int sum = 0; while(isdigit(*exp)) {//计算操作数的值 sum = sum * 10 + (*exp - '0'); exp++; } if (!flag) //如果是负数 { sum = -sum; } OPND.push(sum); flag = 1; } else {//如果不是数字 switch(precede(symbol[OPTR.top()], *exp))//比较栈顶运算符和当前运算符的优先级 { case '>' : b = OPND.top(); OPND.pop(); a = OPND.top(); OPND.pop(); theta = OPTR.top(); OPTR.pop(); OPND.push(figure(a, theta, b)); break; case '<' : OPTR.push(get(*exp)); if(*exp) { exp++; } break; case '=' : OPTR.pop(); if(*exp) { exp++; } break; } } index = OPTR.top(); } return OPND.top(); } int main() { char c[50] = {0}; cout << "请输入一个表达式: "; cin.getline(c,50); cout << EvaluateExpression(c) << endl; return 0; }
队列的应用
舞伴问题
1、问题叙述
假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者，等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。
2、问题分析
先入队的男士或女士亦先出队配成舞伴。因此该问题具体有典型的先进先出特性，可用队列作为算法的数据结构。
在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他（或她）将是下一轮舞曲开始时第一个可获得舞伴的人。
3、具体算法及相关的类型定义
#include <queue> //C++中使用队列要包含的头文件 using namespace std; typedef struct { char name[20]; char sex; //性别，'F'表示女性，'M'表示男性 }Person; void DancePartner(Person dancer[],int num) {//结构数组dancer中存放跳舞的男女，num是跳舞的人数。 Person p; queue<Person> Mdancers,Fdancers; for(int i = 0; i < num; i++) {//依次将跳舞者依其性别入队 p=dancer[i]; if(p.sex=='F') Fdancers.push(p); //排入女队 else Mdancers.push(p); //排入男队 } printf("The dancing partners are: \n \n"); while(!(Fdancers.empty()||Mdancers.empty())) { //依次输入男女舞伴名 p=Fdancers.front(); //获取女队第一人 Fdancers.pop(); //出队 printf("%s ",p.name); //打印出队女士名 p=Mdancers.front(); //获取男队第一人 Mdancers.pop(); //出队 printf("%s\n",p.name); //打印出队男士名 } if(!Fdancers.empty()) {//输出女士剩余人数及队头女士的名字 printf("\n There are %d women waitin for the next round.\n",Fdancers.size()); p=Fdancers.front(); //取队头 printf("%s will be the first to get a partner. \n",p.name); } else if(!Mdancers.empty()) {//输出男队剩余人数及队头者名字 printf("\n There are%d men waiting for the next round.\n",Mdancers.size()); p=Mdancers.front(); printf("%s will be the first to get a partner.\n",p.name); } else { printf("There is not person in the queue!"); } }//DancerPartners int main() { Person p[] = {{"A",'F'},{"B",'F'},{"C",'M'},{"D",'M'}}; DancePartner(p,4); }
