本文提供视频链接与测试数据与哦~
运行时请将数据直接粘贴到输入框中。

题目

优先级表

这个我以后再来补充吧😂

表达式求值的算法

具体操作

左图: 优先级为'<', 进行压栈 右图: 优先级为'>', 解出θ, b, a的值, 再存入操作数栈中
左图: 优先级为'=', 弹出运算符栈中的右括号 右图: 优先级为'>', 解出θ, b, a的值, 再存入操作数栈中, 得到表达式的结果

代码: 适用于一位整数的表达式

注意事项

1.比较栈顶元素与ch优先级时, 只有’>‘不需要读入字符ch
2.循环:
do(…){
     … …
} while (ch != ‘#’ || optr.getTop() != ‘#’);
退出条件:
ch为’#’ 且 栈顶为’#’

#include <iostream>
using namespace std;const int MAX_SIZE = 100; // 栈的最大长度/* Stack类模板 */
template <class DataType>
class Stack
{
private:int size;   // 栈的实际大小int top;    // 栈顶DataType* data; // 指向数组的指针
public:/* 异常内部类 */class Full {};class Empty {};/* 无参构造函数  */Stack(){size = MAX_SIZE;top = -1;data = new DataType[MAX_SIZE];}/* 有参构造函数 */Stack(int size){if (size < MAX_SIZE){this->size = size;top = -1;data = new DataType[size];}else{cout << "您输入的值过大, 栈的容量最大为: " << MAX_SIZE << endl;this->size = MAX_SIZE;top = -1;data = new DataType[MAX_SIZE];}}/* 析构函数 */~Stack(){delete[] data;}/* 入栈 */void push(DataType ch){if (isFull()){throw Full();}else{top++;data[top] = ch;}}/* 出栈并返回栈顶元素 */DataType pop(){if (isEmpty()){throw Empty();}else{DataType ch = data[top];top--;return ch;}}/* 获得栈项元素(不出栈) */DataType getTop(){if (isEmpty()){throw Empty();}else{return data[top];}}/* 判断栈是否为空 */bool isEmpty(){return (top == -1);}/* 判断栈是否已满 */bool isFull(){return (top + 1 == size);}/* 将设置栈为空 */void setNull(){top = -1;}/* 从栈底到栈顶依次显示栈中的元素  */void displayStack(){if (!isEmpty()){for (int i = 0; i < top + 1; i++){cout << data[i] << " ";}cout << endl;}else{cout << "栈为空" << endl;}}
};/* 运算符之间的优先关系 (二维数组) */
char compareOperator[7][7] =
{{'>', '>', '<', '<', '<', '>', '>' },{'>', '>', '<', '<', '<', '>', '>' },{'>', '>', '>', '>', '<', '>', '>' },{'>', '>', '>', '>', '<', '>', '>' },{'<', '<', '<', '<', '<', '=', '0' },{'>', '>', '>', '>', '0', '>', '>' },{'<', '<', '<', '<', '<', '0', '=' },
};/*precede()函数功能: 比较两个运算符的优先级参数: a, b中存放待比较的运算符返回char类型: 返回'>'表示a > b，返回'0'表示不可能出现的比较例如: 表达式 precede('#', '*')的值是'<'
*/
char precede(char a, char b)
{int first = -1;int last = -1;switch (a){case '+': first = 0;break;case '-': first = 1;break;case '*': first = 2;break;case '/': first = 3;break;case '(': first = 4;break;case ')': first = 5;break;case '#': first = 6;break;default: first = -1;break;}switch (b){case '+': last = 0;break;case '-': last = 1;break;case '*': last = 2;break;case '/': last = 3;break;case '(': last = 4;break;case ')': last = 5;break;case '#': last = 6;break;default: last = -1;break;}if (first == -1 || last == -1){return '0'; // 返回'0'表示不可能出现的比较}else{return compareOperator[first][last];}
}/*operate()函数功能: 进行实际的运算参数: a, b中分别以整数的形式存放两个待运算的操作数theta中存放代表燥作符的字符返回值: 运算结果以double的形式返回例如:   表达式 operate(7,'-', 2)的值是5
*/
double operate(double a, char theta, double b)
{double result = 0;switch (theta){case '+':result = a + b;break;case '-':result = a - b;break;case '*':result = a * b;break;case '/':result = a / b;break;default: cout << "您的输入有误!" << endl;exit(EXIT_FAILURE);break;}return result;
}/*isOpnd函数功能:   判断字符是否是操作数参数:   c传入一个字符返回值: 如果字符c是操作数则返回真, 否则返回假
*/
bool isOpnd(char c)
{return (c >= '0' && c <= '9');
}/*isOptr函数功能:   判断字符是否是运算符参数:   c传入一个字符返回值: 如果字符c是运算符则返回真, 否则返回假
*/
bool isOptr(char c)
{return (c == '+' || c == '-' || c == '*' || c == '/'|| c == '(' || c == ')' || c == '#');
}/*EvaluateExpression函数功能: 进行表达式计算参数: 无返回值: 返回double型的运算结果, 如果出现异常情况, 终止程序程序过程: 分别定义
*/
double EvaluateExpression()
{Stack<double> opnd; // 定义操作数栈Stack<char> optr;   // 定义运算符栈optr.setNull();opnd.setNull();optr.push('#');char ch;cin >> ch;do{if (isOptr(ch))          // 如果是运算符{switch (precede(optr.getTop(), ch)) // 比较栈顶元素和ch的优先关系{case '<':optr.push(ch);   // 栈顶元素优先级低, 则压入操作符栈cin >> ch;break;case '=':if (ch == ')'){optr.pop();  // 消去一对括号}cin >> ch;break;case '>':            // 栈顶元素优先级高，取出一个运算符，两个操作数，并计算char theta = optr.pop();double b = opnd.pop();double a = opnd.pop();opnd.push(operate(a, theta, b)); // 将计算结果压入操作数栈break;}}else if (isOpnd(ch))     // 如果是操作数{int temp = ch - '0'; // 将字符ch转换为数字 (可以用int来接受)opnd.push(temp);     // 将temp压入操作数栈cin >> ch;}} while (ch != '#' || optr.getTop() != '#');return opnd.getTop();
}int main()
{cout << "请输入一个正整数表达式, 可以输入的字符包括 +-*/()#0123456789" << endl;double result = EvaluateExpression();cout << "计算结果是: " << result << endl;return 0;
}/* 测试数据:
1+3/2-9/(4-1)#            -0.5
2+3*4*(5-2)+6#            44
(4+2)*(3-2)/5#            1.2
*/

代码: 识别多位正数, 小数

思路

先声明处理多位数和小数的变量bits: double bits = 0;
则输入字符ch时:
若ch为数字 ch >= '0' && ch <= '9'

1. 为一位整数: 条件是bits为0
   处理方法:
   opnd.push(numCh);
bits++;

2. 小数: 条件是0<bits<=1
   处理方法:
   double sum = opnd.pop() + numCh * bits;
bits *= 0.1;
opnd.push(sum);

3. 多位整数: 条件是bits>=1
   处理方法:
   double sum = opnd.pop() * 10 + numCh;
opnd.push(sum);

4. 出错

若ch为运算符, 就令bits为0
(遇到符号, 则不是数字了, 将位数清空)

若ch为小数点, 且小数点前面必须为数字(如: 1.2可以, 但*.2和1.2.3不行), 令bits为0.1就可以了。

#include <iostream>
using namespace std;const int MAX_SIZE = 100; // 栈的最大长度/* Stack类模板 */
template <class DataType>
class Stack
{
private:int size;   // 栈的实际大小int top;    // 栈顶DataType* data; // 指向数组的指针
public:/* 异常内部类 */class Full {};class Empty {};/* 无参构造函数  */Stack(){size = MAX_SIZE;top = -1;data = new DataType[MAX_SIZE];}/* 有参构造函数 */Stack(int size){if (size < MAX_SIZE){this->size = size;top = -1;data = new DataType[size];}else{cout << "您输入的值过大, 栈的容量最大为: " << MAX_SIZE << endl;this->size = MAX_SIZE;top = -1;data = new DataType[MAX_SIZE];}}/* 析构函数 */~Stack(){delete[] data;}/* 入栈 */void push(DataType ch){if (isFull()){throw Full();}else{top++;data[top] = ch;}}/* 出栈并返回栈顶元素 */DataType pop(){if (isEmpty()){throw Empty();}else{DataType ch = data[top];top--;return ch;}}/* 获得栈项元素(不出栈) */DataType getTop(){if (isEmpty()){throw Empty();}else{return data[top];}}/* 判断栈是否为空 */bool isEmpty(){return (top == -1);}/* 判断栈是否已满 */bool isFull(){return (top + 1 == size);}/* 将设置栈为空 */void setNull(){top = -1;}/* 从栈底到栈顶依次显示栈中的元素  */void displayStack(){if (!isEmpty()){for (int i = 0; i < top + 1; i++){cout << data[i] << " ";}cout << endl;}else{cout << "栈为空" << endl;}}
};/* 运算符之间的优先关系 (二维数组) */
char compareOperator[7][7] =
{{'>', '>', '<', '<', '<', '>', '>' },{'>', '>', '<', '<', '<', '>', '>' },{'>', '>', '>', '>', '<', '>', '>' },{'>', '>', '>', '>', '<', '>', '>' },{'<', '<', '<', '<', '<', '=', '0' },{'>', '>', '>', '>', '0', '>', '>' },{'<', '<', '<', '<', '<', '0', '=' },
};/*precede()函数功能: 比较两个运算符的优先级参数: a, b中存放待比较的运算符返回char类型: 返回'>'表示a > b，返回'0'表示不可能出现的比较例如: 表达式 precede('#', '*')的值是'<'
*/
char precede(char a, char b)
{int first = -1;int last = -1;switch (a){case '+': first = 0;break;case '-': first = 1;break;case '*': first = 2;break;case '/': first = 3;break;case '(': first = 4;break;case ')': first = 5;break;case '#': first = 6;break;default: first = -1;break;}switch (b){case '+': last = 0;break;case '-': last = 1;break;case '*': last = 2;break;case '/': last = 3;break;case '(': last = 4;break;case ')': last = 5;break;case '#': last = 6;break;default: last = -1;break;}if (first == -1 || last == -1){return '0'; // 返回'0'表示不可能出现的比较}else{return compareOperator[first][last];}
}/*operate()函数功能: 进行实际的运算参数: a, b中分别以整数的形式存放两个待运算的操作数theta中存放代表燥作符的字符返回值: 运算结果以double的形式返回例如:   表达式 operate(7,'-', 2)的值是5
*/
double operate(double a, char theta, double b)
{double result = -1;switch (theta){case '+':result = a + b;break;case '-':result = a - b;break;case '*':result = a * b;break;case '/':result = a / b;break;default: cout << "您的输入有误!" << endl;exit(EXIT_FAILURE);break;}return result;
}/*isOpnd函数功能:   判断字符是否是操作数参数:   c传入一个字符返回值: 如果字符c是操作数则返回真, 否则返回假
*/
bool isOpnd(char c)
{return (c >= '0' && c <= '9');
}/*isOptr函数功能:   判断字符是否是运算符参数:   c传入一个字符返回值: 如果字符c是运算符则返回真, 否则返回假
*/
bool isOptr(char c)
{return (c == '+' || c == '-' || c == '*' || c == '/'|| c == '(' || c == ')' || c == '#');
}/*EvaluateExpression函数功能: 进行表达式计算参数: 无返回值: 返回double型的运算结果, 如果出现异常情况, 终止程序
*/
double EvaluateExpression()
{Stack<double> opnd; // 定义操作数栈Stack<char> optr;   // 定义运算符栈optr.setNull();opnd.setNull();optr.push('#');double bits = 0;       // 表示数字的位数char ch;cin >> ch;do{if (ch == ' '){cin >> ch;}else if (ch == '.' && bits >= 1) // 小数点前面必须为数字!(如: 1.2可以, *.2不可以){bits = 0.1;cin >> ch;}else if (isOptr(ch))      // 如果是运算符{bits = 0;             // 遇到符号, 则不是数字了, 将位数清空switch (precede(optr.getTop(), ch)) // 比较栈顶元素和ch的优先关系{case '<':optr.push(ch);    // 栈顶元素优先级低, 则压入操作符栈cin >> ch;break;case '=':if (ch == ')'){optr.pop();   // 消去一对括号}cin >> ch;break;case '>':             // 栈顶元素优先级高，取出一个运算符，两个操作数，并计算{                     // 在case里面声明了变量, 要用大括号块{}把这个case内的代码括起来 !!!char theta = optr.pop();double b = opnd.pop();double a = opnd.pop();opnd.push(operate(a, theta, b)); // 将计算结果压入操作数栈break;}default:              // 或者case '0': 表示程序出错, '0'表示不可能出现的比较cout << "程序出错, 您输入的表达式有误!!!" << endl;exit(EXIT_FAILURE);break;}}else if (isOpnd(ch))      // 如果是操作数{double numCh = ch - '0'; // 将字符ch转换为数字 if (bits == 0)        // 一位整数{opnd.push(numCh); bits++;cin >> ch;}else if (bits > 0 && bits < 1){                     // 判断小数。(但1.23.4, 再会判断1.23是否为整数, 若不是, 则报错)double sum = opnd.pop() + numCh * bits;bits *= 0.1;opnd.push(sum);cin >> ch;}else if (bits >= 1)   // 识别多位整数{double sum = opnd.pop() * 10 + numCh;opnd.push(sum);cin >> ch;}else{cout << "程序出错, 您输入的表达式有误!!!" << endl;exit(EXIT_FAILURE);}}else   // 如果输入的ch不是数字, 运算符, 小数点, 空格, 则输入有误, 程序终止{cout << "程序出错, 您输入的表达式有误!!!" << endl;exit(EXIT_FAILURE);}} while (ch != '#' || optr.getTop() != '#');return opnd.getTop();
}int main()
{cout << "请输入一个非负表达式, 可以输入的字符包括 +-*/()#0123456789" << endl;double result = EvaluateExpression();cout << "计算结果是: " << result << endl;return 0;
}/* 测试数据:
2+3*4*(5-2)+6#                        44
2   +3 *9 #                           29
23*(2+5)+62/3#                        181.667
23  *4 5+2#                           1037
@345+6#                               错误
#34/3#                                11.3333
12.25*(4.1-2.5)/(6-4.233)+4#          15.0922
(24+4)/(3.5*6/3)#                     4
123*8+.23#                            错误
1+2.3.3#                              错误1 + 3 * 5 / 4 * 8 / 9 * 6 * 2 / 3 / 7 + 3 * 8 / 2 #            14.9048
985211*985/211#                       4.59921e+06
*/

代码: 完整版, 可以识别负数

处理负号
情况:
1. 第一个字符为负号
2. 括号内的负数: str[i-1] == ‘-’;
处理方法: 0 - 正数
1. 先将0存入opnd栈
2. 再把’-‘存入optr栈

注意: 在这个代码里我把表达式的结尾的’#‘改为了’=’, 这样更加符合实际;
另外用string类型来代替每次要cin >> ch; 这样主要是为了用erase函数来删除表达式中的空格便于后续的处理。

#include <iostream>
#include <string>
using namespace std;const int MAX_SIZE = 100; // 栈的最大长度/* Stack类模板 */
template <class DataType>
class Stack
{
private:int size;   // 栈的实际大小int top;    // 栈顶DataType* data; // 指向数组的指针
public:/* 异常内部类 */class Full {};class Empty {};/* 无参构造函数  */Stack(){size = MAX_SIZE;top = -1;data = new DataType[MAX_SIZE];}/* 有参构造函数 */Stack(int size){if (size < MAX_SIZE){this->size = size;top = -1;data = new DataType[size];}else{cout << "您输入的值过大, 栈的容量最大为: " << MAX_SIZE << endl;this->size = MAX_SIZE;top = -1;data = new DataType[MAX_SIZE];}}/* 析构函数 */~Stack(){delete[] data;}/* 入栈 */void push(DataType ch){if (isFull()){throw Full();}else{top++;data[top] = ch;}}/* 出栈并返回栈顶元素 */DataType pop(){if (isEmpty()){throw Empty();}else{DataType ch = data[top];top--;return ch;}}/* 获得栈项元素(不出栈) */DataType getTop(){if (isEmpty()){throw Empty();}else{return data[top];}}/* 判断栈是否为空 */bool isEmpty(){return (top == -1);}/* 判断栈是否已满 */bool isFull(){return (top + 1 == size);}/* 将设置栈为空 */void setNull(){top = -1;}/* 从栈底到栈顶依次显示栈中的元素  */void displayStack(){if (!isEmpty()){for (int i = 0; i < top + 1; i++){cout << data[i] << " ";}cout << endl;}else{cout << "栈为空" << endl;}}
};/* 运算符之间的优先关系 (二维数组) */
char compareOperator[7][7] =
{{'>', '>', '<', '<', '<', '>', '>' },{'>', '>', '<', '<', '<', '>', '>' },{'>', '>', '>', '>', '<', '>', '>' },{'>', '>', '>', '>', '<', '>', '>' },{'<', '<', '<', '<', '<', '=', '0' },{'>', '>', '>', '>', '0', '>', '>' },{'<', '<', '<', '<', '<', '0', '=' },
};/*precede()函数功能: 比较两个运算符的优先级参数: a, b中存放待比较的运算符返回char类型: 返回'>'表示a > b，返回'0'表示不可能出现的比较例如: 表达式 precede('=', '*')的值是'<'
*/
char precede(char a, char b)
{int first = -1;int last = -1;switch (a){case '+': first = 0;break;case '-': first = 1;break;case '*': first = 2;break;case '/': first = 3;break;case '(': first = 4;break;case ')': first = 5;break;case '=': first = 6;break;default: first = -1;break;}switch (b){case '+': last = 0;break;case '-': last = 1;break;case '*': last = 2;break;case '/': last = 3;break;case '(': last = 4;break;case ')': last = 5;break;case '=': last = 6;break;default: last = -1;break;}if (first == -1 || last == -1){return '0'; // 返回'0'表示不可能出现的比较}else{return compareOperator[first][last];}
}/*operate()函数 例如:表达式 operate(7, '-', 2)的值是5
*/
double operate(double a, char theta, double b)
{double result = -1;switch (theta){case '+':result = a + b;break;case '-':result = a - b;break;case '*':result = a * b;break;case '/':result = a / b;break;default: cout << "您的输入有误!" << endl;exit(EXIT_FAILURE);break;}return result;
}/*EvaluateExpression函数功能: 进行表达式计算参数: 字符串返回值: 返回double型的运算结果, 如果出现异常情况, 终止程序
*/
double EvaluateExpression(string str)
{for (int i = 0; i < str.length(); i++){if (str[i] == ' '){str.erase(i, 1);  // 删去所有空格i--;}}Stack<double> opnd; // 定义操作数栈Stack<char> optr;   // 定义运算符栈optr.setNull();opnd.setNull();optr.push('=');double bits = 0;    // 表示数字的位数int i = 0;if (str[0] == '-')  // 处理第一个字符为负号的情况 {opnd.push(0);optr.push('-');i = 1;}for (; i < str.length() && (str[i] != '=' || optr.getTop() != '='); i++){if (str[i] == '.' && bits >= 1) // 小数点前面必须为数字!(但不能是此数不是小数){bits = 0.1;}else if (str[i] == '-' && str[i - 1] == '('){                         // 处理括号内的负数: (-2)*(-2)opnd.push(0);optr.push('-');}else if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/'|| str[i] == '(' || str[i] == ')' || str[i] == '='){bits = 0;             // 遇到符号, 则不是数字了, 将位数清空switch (precede(optr.getTop(), str[i])) // 比较栈顶元素和ch的优先关系{case '<':optr.push(str[i]);// 栈顶元素优先级低, 则压入操作符栈break;case '=':if (str[i] == ')'){optr.pop();   // 消去一对括号}break;case '>':             // 栈顶元素优先级高，取出一个运算符，两个操作数，并计算{                     // 在case里面声明了变量, 要用大括号块{}把这个case内的代码括起来 !!!char theta = optr.pop();double b = opnd.pop();double a = opnd.pop();opnd.push(operate(a, theta, b)); // 将计算结果压入操作数栈i--;break;}default:cout << "程序出错, 您输入的表达式有误!!!" << endl;exit(EXIT_FAILURE);break;}}else if (str[i] >= '0' && str[i] <= '9'){double numCh = str[i] - '0'; // 将字符ch转换为数字 if (bits == 0){opnd.push(numCh);bits++;}else if (bits > 0 && bits < 1){                          // 判断小数, 例如1.23.4, 会判断1.23是否为整数, 若不是, 则报错double sum = opnd.pop() + numCh * bits;bits *= 0.1;opnd.push(sum);}else if (bits >= 1){double sum = opnd.pop() * 10 + numCh;opnd.push(sum);}else{cout << "程序出错, 您输入的表达式有误!!!" << endl;exit(EXIT_FAILURE);}}else   // 如果输入的ch不是数字, 运算符, 小数点, 空格, 则输入有误, 程序终止{cout << "程序出错, 您输入的表达式有误!!!" << endl;exit(EXIT_FAILURE);}}return opnd.getTop();
}int main()
{string str;cout << "请输入一个非负表达式, 可以输入的字符包括 +-*/()=0123456789" << endl;getline(cin, str);double result = EvaluateExpression(str);cout << "计算结果是: " << result << endl;return 0;
}/* 测试数据:
2+3*4*(5-2)+6=                        44
2   +3 *9 =                           29
23*(2+5)+62/3=                        181.667
23  *4 5+2=                           1037
@345+6=                               错误
=34/3=                                错误
12.25*(4.1-2.5)/(6-4.233)+4=          15.0922
(24+4)/(3.5*6/3)=                     4
123*8+.23=                            错误
1+2.3.3=                              错误1 + 3 * 5 / 4 * 8 / 9 * 6 * 2 / 3 / 7 + 3 * 8 / 2 =            14.9048
985211*985/211=                       4.59921e+06
*//* 处理负号情况:1. 第一个字符为负号2. 括号内的负数: str[i-1] == '-';处理方法: 0 - 正数1. 将0存入opnd栈2. 将'-'存入optr栈测试数据:-1 + ( - 2)* 2-5=                         -10
(-24+ 4 ) /(-3.5*6/(-3 ))*4=                -11.4286
(-12.25)*(- 4.1-2.5)/(-6- 4.233)+4=         -3.90091
*/