-
表达式求值
2018-07-13 18:38:54这里对严蔚敏版的数据结构一书中表达式求值算法给出代码实现.具体参见严蔚敏版数据结构表达式取值章节.表达式求值 实际使用栈来做, 也就是说 , 表达式求值实际是栈的应用 . 这里采用 " 算符 优先法" 对...这里对严蔚敏版的数据结构一书中表达式求值算法给出代码实现.
具体参见严蔚敏版数据结构表达式取值章节.
表达式求值 实际使用栈来做, 也就是说 , 表达式求值实际是栈的应用 . 这里采用 " 算符 优先法" 对表达式求值.代码里实现的是基于加减乘除的整数运算 . 没有对表达式出错情况进行处理. 如果读者需要出错处理 , 在Precede()函数里返回0的代表表达式出错 . 读者可依据返回值自行处理 .
本算法使用两个工作栈 , SqStack_OPTR工作栈 , 用来存放运算符 . SqStack_OPND工作栈 , 用来存放操作数或运算结果 . 因为一个表达式根本上就是由运算符和操作数组成 , 所以这里用到了两个工作栈.
表达式以#开始 , 以#结束 . 开始的#不由用户输入 , 代码 里在创建栈是自动加入 . 结束的#号用户手动输入 , 用来表示一个表达式的结束 .
具体的算法思路不在这里解释了 ,写了一下午了, 脖子有点疼 .
给出算符优先级表 , Precede()函数依据算符优先级表来确定两个操作数的关系 .
算符优先关系表 + - * / ( ) # + > > < < < > > - > > < < < > > * > > > > < > > / > > > > < > > ( < < < < < = 0 ) > > > > 0 > > # < < < < < 0 = 具体代码如下:
#include<iostream> #include<stdlib.h> #define STACK_INIT_SIZE 100 //存储空间初始分配量 #define STACKINCREMENT 10 //存储空间增量 using namespace std; typedef struct { int *base; //栈底指针 ,构造前和销毁后都为NULL int *top; //栈顶指针 int stacksize ; //当前以分配的存储空间 } SqStack_OPND; typedef struct { char *base; //栈底指针 ,构造前和销毁后都为NULL char *top; //栈顶指针 int stacksize ; //当前以分配的存储空间 } SqStack_OPTR; bool InitStack_OPND(SqStack_OPND &s) { //构造一个空栈 s.base = (int*) malloc(STACK_INIT_SIZE * sizeof(int) ) ; if(!s.base) return false; s.top = s.base; s.stacksize = STACK_INIT_SIZE; return true; } bool InitStack_OPTR(SqStack_OPTR &s) { //构造一个空栈 s.base = (char*) malloc(STACK_INIT_SIZE * sizeof(char) ) ; if(!s.base) return false; s.top = s.base; s.stacksize = STACK_INIT_SIZE; return true; } char GetTop_OPTR(SqStack_OPTR &s ) { //若栈不为空,返回字符e ,否则返回数值0 char e; if(s.top == s.base) return 0; e = *(s.top-1); return e; } char GetTop_OPND(SqStack_OPND &s ) { //若栈不为空,返回字符e ,否则返回数值0 int e; if(s.top == s.base) return 0; e = *(s.top-1); return e; } bool Push_OPTR(SqStack_OPTR &s , char e) { //插入e为新的栈顶元素 if(s.top - s.base > s.stacksize) { //栈满,追加存储空间 s.base = (char*) realloc(s.base , (s.stacksize + STACKINCREMENT) * sizeof(char) ); if(!s.base) return false; s.top = s.base + s.stacksize; s.stacksize += STACKINCREMENT; } //增加空间完毕 *s.top++ = e; return true; } bool Push_OPND(SqStack_OPND &s , int e) { //插入e为新的栈顶元素 if(s.top - s.base > s.stacksize) { //栈满,追加存储空间 s.base = (int*) realloc(s.base , (s.stacksize + STACKINCREMENT) * sizeof(int) ); if(!s.base) return false; s.top = s.base + s.stacksize; s.stacksize += STACKINCREMENT; } //增加空间完毕 *s.top++ = e; return true; } bool Pop_OPTR(SqStack_OPTR &s , char &e) { //若栈不为空,删除s的栈顶元素,用e返回其值,并返回true , 否则返回false if(s.top == s.base) return false; e = * --s.top; return true; } bool Pop_OPND(SqStack_OPND &s , int &e) { //若栈不为空,删除s的栈顶元素,用e返回其值,并返回true , 否则返回false if(s.top == s.base) return false; e = * --s.top; return true; } //定义两个工作栈 //用来寄存运算符的栈 : OPTR //用来寄存操作数或运算结果的栈 : OPND SqStack_OPTR OPTR ; SqStack_OPND OPND ; int e; //接收栈顶元素 GetTop() 和 Pop()中用到 char Precede(char e , char c) //根据算符优先关系表,返回三个优先关系之一 { //规定, e 为01 ,c 为 02 int convert_e , convert_c; //将e 和 c 转换为数字在进行比较,方便代码书写和理解 //对e 进行转换 switch(e) { case '+' : convert_e = 1 ; break; case '-' : convert_e = 2 ; break; case '*' : convert_e = 3 ; break; case '/' : convert_e = 4 ; break; case '(' : convert_e = 5 ; break; case ')' : convert_e = 6 ; break; case '#' : convert_e = 7 ; break; } //对c 进行转换 switch(c) { case '+' : convert_c = 1 ; break; case '-' : convert_c = 2 ; break; case '*' : convert_c = 3 ; break; case '/' : convert_c = 4 ; break; case '(' : convert_c = 5 ; break; case ')' : convert_c = 6 ; break; case '#' : convert_c = 7 ; break; } if(convert_e == 1 && convert_c == 1) return '>'; if(convert_e == 1 && convert_c == 2) return '>'; if(convert_e == 1 && convert_c == 3) return '<'; if(convert_e == 1 && convert_c == 4) return '<'; if(convert_e == 1 && convert_c == 5) return '<'; if(convert_e == 1 && convert_c == 6) return '>'; if(convert_e == 1 && convert_c == 7) return '>'; if(convert_e == 2 && convert_c == 1) return '>'; if(convert_e == 2 && convert_c == 2) return '>'; if(convert_e == 2 && convert_c == 3) return '<'; if(convert_e == 2 && convert_c == 4) return '<'; if(convert_e == 2 && convert_c == 5) return '<'; if(convert_e == 2 && convert_c == 6) return '>'; if(convert_e == 2 && convert_c == 7) return '>'; if(convert_e == 3 && convert_c == 1) return '>'; if(convert_e == 3 && convert_c == 2) return '>'; if(convert_e == 3 && convert_c == 3) return '>'; if(convert_e == 3 && convert_c == 4) return '>'; if(convert_e == 3 && convert_c == 5) return '<'; if(convert_e == 3 && convert_c == 6) return '>'; if(convert_e == 3 && convert_c == 7) return '>'; if(convert_e == 4 && convert_c == 1) return '>'; if(convert_e == 4 && convert_c == 2) return '>'; if(convert_e == 4 && convert_c == 3) return '>'; if(convert_e == 4 && convert_c == 4) return '>'; if(convert_e == 4 && convert_c == 5) return '<'; if(convert_e == 4 && convert_c == 6) return '>'; if(convert_e == 4 && convert_c == 7) return '>'; if(convert_e == 5 && convert_c == 1) return '<'; if(convert_e == 5 && convert_c == 2) return '<'; if(convert_e == 5 && convert_c == 3) return '<'; if(convert_e == 5 && convert_c == 4) return '<'; if(convert_e == 5 && convert_c == 5) return '<'; if(convert_e == 5 && convert_c == 6) return '='; if(convert_e == 5 && convert_c == 7) return '0'; //出现语法错误是返回字符0 因为 ( 和 # 不允许相继出现 if(convert_e == 6 && convert_c == 1) return '>'; if(convert_e == 6 && convert_c == 2) return '>'; if(convert_e == 6 && convert_c == 3) return '>'; if(convert_e == 6 && convert_c == 4) return '>'; if(convert_e == 6 && convert_c == 5) return '0'; // 不允许出现 ) ( 的形式 if(convert_e == 6 && convert_c == 6) return '>'; if(convert_e == 6 && convert_c == 7) return '>'; if(convert_e == 7 && convert_c == 1) return '<'; if(convert_e == 7 && convert_c == 2) return '<'; if(convert_e == 7 && convert_c == 3) return '<'; if(convert_e == 7 && convert_c == 4) return '<'; if(convert_e == 7 && convert_c == 5) return '<'; if(convert_e == 7 && convert_c == 6) return '0'; //# 和 ( 不允许同时相继出现 if(convert_e == 7 && convert_c == 7) return '='; } //Precede char theta; // 在Precede()函数判出> 的情况下, 存放从OPTR中出栈的运算符 //返回运算结果 theta为操作数 a 和 b 为运算符左值 和 右值 int Operate(int a , char theta , int b) { switch(theta) { case '+' : return a+b; case '-' : return a-b; case '*' : return a*b; case '/' : return a/b; } } bool In(char c) { switch(c) { case '+' : case '-' : case '*' : case '/' : case '(' : case ')' : case '#' : return true; } return false; } int EvaluateExpression() //int 是返回表达式运算后的最终结果 { char c; InitStack_OPTR(OPTR); Push_OPTR(OPTR , '#'); InitStack_OPND(OPND); c = getchar(); while( c != '#' || GetTop_OPTR(OPTR) != '#') { if(!In(c)) { Push_OPND(OPND , c-48); c =getchar(); //不是运算符则进栈 } else { switch( Precede(GetTop_OPTR(OPTR) , c) ) { case '<': //栈顶元素优先权低 { Push_OPTR(OPTR , c) ; c = getchar(); break; } case '=': //脱括号并接收下一个字符 { char x; //接收退栈后的值 Pop_OPTR(OPTR , x) ; c = getchar(); break; } case '>': //退栈并将结果存入栈 { int a ,b; Pop_OPTR(OPTR , theta); Pop_OPND(OPND , b); Pop_OPND(OPND ,a); Push_OPND(OPND , Operate(a ,theta ,b)); break; } }//switch } } //while return GetTop_OPND(OPND); } int main() { cout<<"输入表达式,得出运算结果,输入以#结束,输入完毕请按回车!"<<endl; int result = EvaluateExpression(); cout<<"表达式结果为:"<<endl; cout<<result<<endl; return 0; }
运行结果图:
-
表达式求值,一次完全理解透彻:求前缀表达式求值,后缀表达式(逆波兰表达式)求值 还有中缀表达式求值
2020-04-18 16:20:09表达式求值前缀表达式题目:方法一 :非常巧妙方法2:采用递归后缀表达式中缀表达式思路 前缀表达式 题目: 求前缀表达式的值 (25point(s)) 算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。前缀表达式指...前缀表达式
题目:
求前缀表达式的值 (25point(s))
算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。前缀表达式指二元运算符位于两个运算数之前,例如2+3*(7-4)+8/4的前缀表达式是:+ + 2 * 3 - 7 4 / 8 4。请设计程序计算前缀表达式的结果值。输入格式:
输入在一行内给出不超过30个字符的前缀表达式,只包含+、-、*、/以及运算数,不同对象(运算数、运算符号)之间以空格分隔。输出格式:
输出前缀表达式的运算结果,保留小数点后1位,或错误信息ERROR。输入样例:
+ + 2 * 3 - 7 4 / 8 4
输出样例:
13.0
方法一 :非常巧妙
前缀表达式咋看上去与后缀表达式不一样,没办法用栈处理直接求值,其实是可以的。我只要改变下表达式的扫描方式,从右往左扫描,就变成了了后缀表达式。
从左往右扫描:
- 如果是数字,转换为数字入栈;
- 如果是字符,弹出栈顶两数运算,计算结果入栈
- 直到序列扫描完毕,如果栈正好剩下一个元素,就是最终计算结果
是不是非常巧妙!
代码如下://方法1 //使用字符串流stringstream对double和string进行相互转换 //也可以用string的全局函数:double->string,使用std::to_string, string→double使用std::stod //前缀运算符,从后往前将数字压入stack,遇到操作符则弹出两个数字进行运算 //把输入的每个数当成浮点型运算,每次读入一个单词到string,使用vector保存 #include<iostream> #include<stack> #include<vector> #include<string> #include<iomanip> using std::cin; using std::cout; using std::endl; using std::stod; bool isOp(std::string s) { if (s == "+" || s == "-" || s == "*" || s == "/") return true; else return false; } int main() { std::string str; std::vector<std::string> vec; while (cin.peek() != '\n') { cin >> str; vec.push_back(str); } int n = vec.size(); std::stack<double> sstack; double a = 0, b = 0; //我写成int a,b了 for (int i = n - 1; i >= 0; i--) { //从右往左扫描,如果是数字,转换为数字入栈;如果是字符,栈顶弹出两数运算,结果入栈 if (!isOp(vec[i])) sstack.push(stod(vec[i])); //如果是数字,直接入栈 else { //如果是符号,弹出两个数参与运算,且把结果入栈 if (sstack.size() < 2) { cout << "ERROR" << endl; break; //return 0;也行 } a = sstack.top(); sstack.pop(); b = sstack.top(); sstack.pop(); //switch (vec[i]) //条件表达式必须是整型或者枚举类型, 字符串类型是不行的 switch (vec[i][0]) { //所以用字符类型 case '+': sstack.push(a + b); break; case '-': sstack.push(a - b); break; case '*': sstack.push(a * b); break; case '/': //忘了除数可能为0 if (b == 0) { cout << "ERROR" << endl; return 0; } sstack.push(a / b); break; default: cout << "ERROR" << endl; break; } } } //最后扫描完了,栈中应该只剩一个数,就是结果 if (sstack.size() == 1) cout << std::fixed <<std::setprecision(1) << sstack.top() << endl; else cout << "ERROR" << endl; return 0; }
方法2:采用递归
后缀表达式
后缀表达式的求值,跟前缀表达式求值方法1一模一样,它从左往右扫描,
- 如果碰到的数字,入栈
- 如果碰到的是运算符,弹出栈顶两数参与运算,计算结果入栈
中缀表达式
我先将中缀表达式转换为后缀表达式。
习题3.11 表达式转换 (25point(s))
算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法,即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。输入格式:
输入在一行中给出不含空格的中缀表达式,可包含+、-、*、\以及左右括号(),表达式不超过20个字符。输出格式:
在一行中输出转换后的后缀表达式,要求不同对象(运算数、运算符号)之间以空格分隔,但结尾不得有多余空格。输入样例:
2+3*(7-4)+8/4
输出样例:
2 3 7 4 - * + 8 4 / +
思路
用map<char,int>来比较优先级,思维导图如下:对于碰到的序列字符a[i]
//用map<char,int>来比较优先级 #include<iostream> #include<string> #include<stack> #include<map> using namespace std; int main() { string str; stack<char> s; cin >> str; //因为表达式中间无空格,读入了整个表达式 //优先级 map<char, int>p; p['+'] = p['-'] = 0; p['*'] = p['/'] = 1; p['('] = p[')'] = 2; int flag = 0;//用来控制队首不输出空格 for (int i = 0; i < str.length(); i++) { //str[i]两种情况,一种是数字或正负号, 一种是符号 if (((i == 0 || str[i - 1] == '(') && (str[i] == '+' || str[i] == '-')) || (str[i] >= '0' && str[i] <= '9')) { if (flag)//flag==0时,就不输出空格了 cout << " "; flag = 1; if (str[i] != '+')cout << str[i];//a[i]是正号就不用输出了,必须有这句,不然报错了 while (str[i + 1] == '.' || (str[i + 1] >= '0' && str[i + 1] <= '9')) {//如果接下来是.或者数字,继续读 i++; cout << str[i]; } } else {//str[i]是符号 三种情况,1.只出栈不入栈情况:右括号,2.只入栈不出栈的情况:栈空或者栈顶优先级小于a[i] //3.入栈+出栈:栈顶优先级>=a[i],不能是左括号 if (str[i] == ')') {//1.只出栈不入栈情况:右括号 while (!s.empty()&&s.top()!='(') { cout << " " << s.top(); s.pop(); } s.pop();//弹出左括号 } else if (s.size() == 0 || p[s.top()] < p[str[i]]) {//只入栈不出栈的情况:栈空或者栈顶优先级小于a[i] s.push(str[i]); } else {//3.入栈+出栈:栈顶优先级>=a[i],不能是左括号 while (!s.empty() && s.top() != '(' && p[s.top()] >= p[str[i]]) { cout << " " << s.top(); s.pop(); } s.push(str[i]); } } } //到最后,如果栈不空,弹出即可 while (!s.empty()) { cout << " " << s.top(); s.pop(); } cout << endl; return 0; }
-
Kotlin协程极简入门与解密
-
iphone4S维修原理图PCB位置图(PDF格式)
-
Excel高级图表技巧
-
iphone5维修原理图PCB位置图(PDF格式)
-
模式识别第四版答案
-
一个程序员的自述
-
Pytorch.zip
-
nfcPro_kgf_v6.exe
-
【数据分析-随到随学】机器学习模型及应用
-
剑指 Offer 06. 从尾到头打印链表题解
-
SCE 11.0x-Word Specification_OTZ_20210117.pdf
-
1/23~调和级数lqb
-
node.js基础-06npm和yarn的基础操作
-
iPad 5 air维修原理图PCB位置图(PDF格式)
-
字体ttf大全.rar
-
QT定时器的使用
-
ioe
-
python办公自动化技巧
-
深入理解CAS
-
通用功能开发