复兴提高班第十九课 表达式与表达式求值
2025-10-18 20:34:28
发布于：上海
4阅读
0回复
0点赞
T1【表达式求值】中缀表达式转后缀表达式
#include<bits/stdc++.h>
using namespace std;
const int maxSize = 109;
//判断运算符的优先级
int getPriority(char op) {
if (op == '+' || op == '-')
return 0; //+或-的优先级比较低
else
return 1;
}
void infixToPostFix(char infix[], char s2[], int& top2) //infix[]是中缀表达式存在数组里，s2是结果栈
{
char s1[maxSize]; int top1 = -1; //s1是辅助栈
int i = 0;
while (infix[i] != '\0') {
if ('a' <= infix[i] && infix[i] <= 'z') { //如果扫描到'a'-'z'字符，将它放入s2
s2[++top2] = infix[i];
++i;
}
else if (infix[i] == '(') { //如果扫描到'('，将它放入s1
s1[++top1] = '(';
++i;
}
else if (infix[i] == '+' || //如果扫描到'+','-','*','/'字符，需要和s1里的元素进行判断
infix[i] == '-' ||
infix[i] == '*' ||
infix[i] == '/') {
if (top1 == -1 || //判断s1是否为空
s1[top1] == '(' || //判断辅助栈的栈顶元素是否为'('
getPriority(infix[i]) > getPriority(s1[top1])) { //判断表达式里元素的优先级是否大于s1元素的优先级
s1[++top1] = infix[i];
++i;
}
else //如果不是，将辅助栈的运算符放入结果栈里
s2[++top2] = s1[top1--];
}
else if (infix[i] == ')') {
while (s1[top1] != '(')
s2[++top2] = s1[top1--];
--top1; //删除s1里的'('
++i;
}
}
while (top1 != -1)
s2[++top2] = s1[top1--]; //将s1中的元素都放入s2
}
char s[109], res[109];
int main() {
cin >> s;
int len = -1;
infixToPostFix(s, res, len);
for (int i = 0; i <= len; i++) cout << res[i];
return 0;
}
T2【表达式求值】中缀表达式转前缀表达式
#include<bits/stdc++.h>
using namespace std;
const int maxSize = 109;
//判断运算符的优先级
int getPriority(char op) {
if (op == '+' || op == '-')
return 0; //+或-的优先级比较低
else
return 1;
}
void infixToPreFix(char infix[], int len, stack<char>& s2) {
stack<char> s1;//符号栈
int i = len - 1;
while (i >= 0) {
if ('a' <= infix[i] && infix[i] <= 'z') {
s2.push(infix[i]);
--i;
}
else if (infix[i] == ')') {
s1.push(infix[i]);
--i;
}
else if (infix[i] == '+' ||
infix[i] == '-' ||
infix[i] == '*' ||
infix[i] == '/') {
if (s1.size() == 0 ||
s1.top() == ')' ||
getPriority(infix[i]) >= getPriority(s1.top())) {
s1.push(infix[i]);
--i;
}
else {
s2.push(s1.top());
s1.pop();
}
}
if (infix[i] == '(') {
while (s1.top() != ')') {
s2.push(s1.top());
s1.pop();
}
s1.pop();
--i;
}
}
while (s1.size()) {
s2.push(s1.top());
s1.pop();
}
}
char s[109];
stack<char> res;
int main() {
cin >> s;
int len = -1;
infixToPreFix(s, strlen(s), res);
while (res.size()) {
cout << res.top();
res.pop();
}
return 0;
}
T3【表达式求值】后缀表达式求值
#include<bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
stack<int> num;
for (int i = 0; i < s.length(); i++) {
if (s[i] >= '0' && s[i] <= '9') {
num.push(s[i] - '0');
}
else {
int r = num.top(); num.pop();
int l = num.top(); num.pop();
if (s[i] == '+') num.push(l + r);
else if (s[i] == '-') num.push(l - r);
else if (s[i] == '*') num.push(l * r);
else num.push(l / r);
}
}
cout << num.top();
return 0;
}
T4【表达式求值】前缀表达式求值
#include<bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
stack<int> st;
for (int i = s.length()-1; i >= 0; i--) {
if (s[i] >= '0' && s[i] <= '9') {
st.push(s[i] - '0');
}
else {
int l = st.top(); st.pop();
int r = st.top(); st.pop();
if (s[i] == '+') {
st.push(l + r);
}
else if (s[i] == '-') {
st.push(l - r);
}
else if (s[i] == '*') {
st.push(l * r);
}
else if (s[i] == '/') {
st.push(l / r);
}
}
}
cout << st.top();
return 0;
}
T5【表达式求值】中缀表达式求值
#include<bits/stdc++.h>
using namespace std;
stack<int> num;
stack<char> op;
int getPriority(char op) {
if (op == '+' || op == '-')
return 0; //+或-的优先级比较低
return 1;
}
void calc() {
int r = num.top(); num.pop();//栈顶是右操作数
int l = num.top(); num.pop();//次栈顶是左操作数
if (op.top() == '+') num.push(l + r);
if (op.top() == '-') num.push(l - r);
if (op.top() == '/') num.push(l / r);
if (op.top() == '*') num.push(l * r);
op.pop();//弹出运算符
}
int main() {
string s;
cin >> s;
for (int i = 0; i < s.length(); i++) {
if (s[i] >= '0' && s[i] <= '9') {
num.push(s[i] - '0');
}
else {
if (s[i] == '(') {
op.push(s[i]);//左括号直接进栈
}
else if (s[i] == '+'||s[i]=='-'||s[i]=='*'||s[i]=='/') {
while (op.size() && op.top()!='('&&getPriority(op.top()) >= getPriority(s[i])) {
calc();
}
op.push(s[i]);
}
else if (s[i] == ')') {
while (op.top() != '(') {
calc();
}
op.pop();//弹出左括号
}
}
}
while (op.size()) {
calc();
}
cout << num.top();
return 0;
}
T6【表达式求值】中缀表达式
#include<bits/stdc++.h>
using namespace std;
const int maxSize = 109;
//判断运算符的优先级
int getPriority(char op) {
if (op == '+' || op == '-')
return 0; //+或-的优先级比较低
else
return 1;
}
void infixToPreFix(char infix[], int len, stack<char>& s2) {
stack<char> s1;//符号栈
int i = len - 1;
while (i >= 0) {
if ('a' <= infix[i] && infix[i] <= 'z') {
s2.push(infix[i]);
--i;
}
else if (infix[i] == ')') {
s1.push(infix[i]);
--i;
}
else if (infix[i] == '+' ||
infix[i] == '-' ||
infix[i] == '*' ||
infix[i] == '/') {
if (s1.size() == 0 ||
s1.top() == ')' ||
getPriority(infix[i]) > getPriority(s1.top())) {
s1.push(infix[i]);
--i;
}
else {
s2.push(s1.top());
s1.pop();
}
}
if (infix[i] == '(') {
while (s1.top() != ')') {
s2.push(s1.top());
s1.pop();
}
s1.pop();
--i;
}
}
while (s1.size()) {
s2.push(s1.top());
s1.pop();
}
}
void infixToPostFix(char infix[], stack<char>& s2) { //infix[]是中缀表达式存在数组里，s2是结果栈
stack<char> s1; //s1是辅助栈
int i = 0;
while (infix[i] != '\0') {
if ('a' <= infix[i] && infix[i] <= 'z') { //如果扫描到'a'-'z'字符，将它放入s2
s2.push(infix[i]);
++i;
}
else if (infix[i] == '(') { //如果扫描到'('，将它放入s1
s1.push(infix[i]);
++i;
}
else if (infix[i] == '+' || //如果扫描到'+','-','*','/'字符，需要和s1里的元素进行判断
infix[i] == '-' ||
infix[i] == '*' ||
infix[i] == '/') {
if (s1.size() == 0 || //判断s1是否为空
s1.top() == '(' || //判断辅助栈的栈顶元素是否为'('
getPriority(infix[i]) > getPriority(s1.top())) { //判断表达式里元素的优先级是否大于s1元素的优先级
s1.push(infix[i]);
++i;
}
else {//如果不是，将辅助栈的运算符放入结果栈里
s2.push(s1.top());
s1.pop();
}
}
else if (infix[i] == ')') {
while (s1.top() != '(') {
s2.push(s1.top());
s1.pop();
}
s1.pop(); //删除s1里的'('
++i;
}
}
while (s1.size()) { //将s1中的元素都放入s2
s2.push(s1.top());
s1.pop();
}
}
char s[109];
stack<char> res;
int main() {
cin >> s;
infixToPreFix(s, strlen(s), res);
while (res.size()) {
cout << res.top();
res.pop();
}
cout << '\n';
infixToPostFix(s, res);
string ans;
while (res.size()) {
ans += res.top();
res.pop();
}
reverse(ans.begin(), ans.end());
cout << ans;
return 0;
}
T7【表达式求值】前缀表达式转后缀表达式
#include<bits/stdc++.h>
using namespace std;
const int maxSize = 109;
//判断运算符的优先级
int getPriority(char op) {
if (op == '+' || op == '-')
return 0; //+或-的优先级比较低
else
return 1;
}
void infixToPostFix(string infix, char s2[], int& top2) //infix[]是中缀表达式存在数组里，s2是结果栈
{
char s1[maxSize]; int top1 = -1; //s1是辅助栈
int i = 0;
while (infix[i] != '\0') {
if ('a' <= infix[i] && infix[i] <= 'z') { //如果扫描到'a'-'z'字符，将它放入s2
s2[++top2] = infix[i];
++i;
}
else if (infix[i] == '(') { //如果扫描到'('，将它放入s1
s1[++top1] = '(';
++i;
}
else if (infix[i] == '+' || //如果扫描到'+','-','*','/'字符，需要和s1里的元素进行判断
infix[i] == '-' ||
infix[i] == '*' ||
infix[i] == '/') {
if (top1 == -1 || //判断s1是否为空
s1[top1] == '(' || //判断辅助栈的栈顶元素是否为'('
getPriority(infix[i]) > getPriority(s1[top1])) { //判断表达式里元素的优先级是否大于s1元素的优先级
s1[++top1] = infix[i];
++i;
}
else //如果不是，将辅助栈的运算符放入结果栈里
s2[++top2] = s1[top1--];
}
else if (infix[i] == ')') {
while (s1[top1] != '(')
s2[++top2] = s1[top1--];
--top1; //删除s1里的'('
++i;
}
}
while (top1 != -1)
s2[++top2] = s1[top1--]; //将s1中的元素都放入s2
}
char res[109];
int main() {
string s;
cin >> s;
stack<string> num;
//先转换为中缀表达式
for (int i = s.length() - 1; i >= 0; i--) {
if (s[i] >= 'a' && s[i] <= 'z') {
num.push(string(1,s[i]));//string(1,s[i])得到一个string类型的字符串仅有一个s[i]
}
else {
string l = num.top(); num.pop();
string r = num.top(); num.pop();
string ans = "(" + l + s[i] + r + ")";
num.push(ans);
}
}
//再转换为后缀表达式
int len = -1;
infixToPostFix(num.top(), res, len);
for (int i = 0; i <= len; i++) cout << res[i];
return 0;
}
这里空空如也
有帮助，赞一个