当前位置：首页 > news >正文

表达式求值问题（中缀转后缀，对后缀求值）详解

news 2024/11/15 10:19:02

实验题目

理解中缀和后缀表达式

问题分析

1转化为中缀表达式

2计算后缀表达式

完整代码

运行结果

实验题目

实验题目：表达式求值问题。这里限定的表达式求值问题是：用户输入一个包含“+”、“-”、“*”、“/”、正整数和圆括号的合法数学表达式，计算该表达式的运算结果。

算术表达式求值过程是： STEP 1：先将算术表达式转换成后缀表达式。

STEP 2：然后对该后缀表达式求值。

实验说明：在设计相关算法中用到栈，这里采用顺序栈存储结构。

中缀表达式exp ==》后缀表达式postexp伪代码如下：

对后缀表达式postexp求值伪代码如下：

理解中缀和后缀表达式

在做本题之前，先了解一下什么是中缀表达式和后缀表达式。

中缀表达式是最常用的算术表达式表示方法，其中操作符位于两个操作数之间。这种表示法符合人们的常规书写习惯，但在计算机处理时可能需要额外的解析步骤，特别是涉及到优先级和括号时。所以要转化为后缀方便计算机计算。

例子：

3+4

(5+3)×2

8/2−1

后缀表达式是一种将操作符放在操作数之后的表示方法。这种表示法的优点是不需要括号来指定运算顺序，因为操作符总是紧跟在其操作数之后。这使得后缀表达式在计算机中更容易解析和计算。

例子：

3+4的后缀表达式为：3 4+

(5+3)×2 的后缀表达式为：5 3 + 2 ×

8/2−1 的后缀表达式为：8 2 / 1−

问题分析

按照题目要求，求解一个表达式分为两步

1转化为中缀表达式

第一步，将一个中缀表达式转化为一个后缀表达式，如果是数字直接存放入p中

1如果是左括号也直接存入。

2当碰到右括号时，要一直出栈直到碰到左括号，最后将左括号也出栈。

3当碰到+号和－号时,如果栈顶不是左括号且栈不为空，就一直出栈并且存放到p中，最后直到不满足前面那一句话就存入加减号。

4如果碰到乘除号，如果栈顶不是左括号，加减号，栈不为空，就一直出栈存放入p中，最后直到不满足前面那一句话就存入乘除号。

总之：只要满足栈空或者优先级高于栈顶操作符即可停止出栈，并将该操作符入栈

2计算后缀表达式

第二步，计算后缀表达式

1 如果是数字，直接入栈

2 如果是运算符，则取出两个数字运算它们再存入栈顶

3 遍历完后缀表达式后，得到的结果即为栈顶的值。

没看懂的可以直接对应着看代码，因为代码里也有注释。

完整代码

#include<bits/stdc++.h>
using namespace std;stack<char> stk;
//创建一个空栈
char str[] = "2*(3+5)+7/1-4";
char p[100];
//s为待转化的中缀字符串，p为转化后的后缀字符串void change() {long long unsigned i;int j = 0;for(i = 0; i < strlen(str); i++) {while(isdigit(str[i])) {//遍历字符串//如果是数字直接输出(存放在p字符串中)p[j++] = str[i++];p[j++] = '#';}//遇到左括号直接入栈if(str[i] == '(')stk.push(str[i]);//遇到右括号直接出栈，直到遇到左括号，最后将左括号也出栈但是不存放入p字符串中if(str[i] == ')') {while(stk.top() != '(') {p[j++] = stk.top();stk.pop();}stk.pop();}//遇到+和-//1栈空和栈顶为左括号直接入栈//2否则一直出栈，直到满足1再入栈if(str[i] == '+' || str[i] == '-') {while(!stk.empty() && stk.top() != '(') {p[j++] = stk.top();stk.pop();}stk.push(str[i]);}//遇到*和///1栈空或栈顶为左括号和+和-入栈//2否则一直出栈，直到满足1再入栈if(str[i] == '*' || str[i] == '/') {while(!stk.empty() && stk.top() != '(' && stk.top() != '+' && stk.top() != '-') {p[j++] = stk.top();stk.pop();}stk.push(str[i]);}}//如果最后栈仍然不为空就直接存入数组p中while(!stk.empty()) {p[j++] = stk.top();stk.pop();}
}//用于计算出后缀表达式的结果
double cal() {double a,b;stack<double> s;//初始化一个运算数栈用于保存运算数for(long long unsigned int i = 0; i < strlen(p); i++) {while(isdigit(p[i])) {s.push(p[i] - '0' + 0.0);//这里将字符转化为数字，直接减去字符0，再加上0.0是再让它转变为一个double类型的
//			cout << p[i] - '0' << endl; 
//			cout << s.top() << endl;i++;i++;//这里多i++一次是为了跳过那个#号}//如果是加减乘除就出栈两个然后分别对它们进行相应的计算然后入栈if(p[i] == '+') {a = s.top();s.pop();b = s.top();s.pop();s.push(a+b);
//			cout << a << ' ' << b << endl;}else if(p[i] == '-') {a = s.top();s.pop();b = s.top();s.pop();s.push(b-a);}else if(p[i] == '*') {a = s.top();s.pop();b = s.top();s.pop();s.push(a*b);}else if(p[i] == '/') {a = s.top();s.pop();b = s.top();s.pop();s.push(b/a);}
//		cout << s.top() << endl;}//最后栈顶就是计算出的结果return s.top();
}int main() {printf("中缀字符串为：%s\n",str);change();printf("转化得到的后缀字符串为：%s\n",p);double ans = cal();cout << "后缀字符串计算得到的结果为：";cout << ans << endl;return 0;
}