学习目标
算数表达式
三种算数表达式
中缀转后缀
计算机的转换逻辑
中缀转后缀
【算法分析】
从左到右进行遍历。
1.遇到的是运算数，直接输出。
2.遇到的是左括号'('，直接压入堆栈(括号是最高优先级，无需比较；入栈后优先级降到最低，确保其他符号正常入栈)。
3.遇到的是右括号')'，意味着括号已结束。不断弹出栈顶运算符并输出，直到遇到左括号，这个左括号弹出但是不输出。
4.遇到的是运算符('+'、'-'、'*'、'/')，有三种情况
①如果栈为空，直接入栈。
②如果栈顶元素是左括号'('，直接入栈。
③如果栈顶元素是运算符，则需要进行比较，
1-如果优先级大于栈顶运算符，则压入堆栈；
2-如果优先级小于等于栈顶运算符，则将栈顶运算符弹出并输出，然后比较新的栈顶运算符，直到优先级大于栈顶运算符或者栈空，再将该运算符入栈
5.如果对象处理完毕，则按顺序弹出并输出栈中所有运算符
【参考代码】
#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;
}
View Code
中缀表达式
[【表达式求值】中缀表达式转前缀表达式]
【算法分析】
中缀转前缀：
从右到左进行遍历。
1.遇到的是运算数，直接输出。
2.遇到的是右括号')'，直接压入堆栈(括号是最高优先级，无需比较；入栈后优先级降到最低，确保其他符号正常入栈)。
3.遇到的是左括号'('，意味着括号已结束。不断弹出栈顶运算符并输出，直到遇到右括号，这个右括号弹出但是不输出。
4.遇到的是运算符('+'、'-'、'*'、'/')，有三种情况
①如果栈为空，直接入栈。
②如果栈顶元素是右括号')'，直接入栈。
③如果栈顶元素是运算符，则需要进行比较，
1-如果优先级大于栈顶运算符，则压入堆栈；
2-如果优先级小于等于栈顶运算符，则将栈顶运算符弹出并输出，然后比较新的栈顶运算符，直到优先级大于等于栈顶运算符或者栈空，再将该运算符入栈
5.如果对象处理完毕，则按顺序弹出并输出栈中所有运算符
【参考代码】
#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;
}
View Code
后缀表达式求值
后缀表达式求值
【算法分析】
从左到右扫描，碰到数字就进栈，碰到操作数就拿出栈顶的两个元素就行运算，栈顶应该是右操作数。
【参考代码】
#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;
}
View Code
前缀表达式求值
【表达式求值】前缀表达式求值]
【算法分析】
从右向左遍历整个字符串，碰到数字就进栈，碰到操作符就进行运算。
【参考代码】
#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;
}
View Code
[【表达式求值】中缀表达式求值]
【算法分析】
从左到右扫描该中缀表达式：
如果遇到数字，直接输出该数字。
如果遇到左括号，那么将其放在运算符栈上。
如果遇到右括号，不断输出栈顶元素，直至遇到左括号，左括号出栈。换句话说，执行一对括号内的所有运算符。
如果遇到其他运算符，不断输出所有运算优先级大于等于当前运算符的运算符。最后，新的运算符入运算符栈。
在处理完整个字符串之后，一些运算符可能仍然在堆栈中，因此把栈中剩下的符号依次输出，表达式转换结束。
【参考代码】
#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;
}
View Code
作业讲解分析：
链接：https://pan.baidu.com/s/1kC35E12wnWnlylu1KIuq9g?pwd=q55c
提取码：q55c
标签：10,优先级,int,s1,栈顶,运算符,求值,表达式,op From： https://www.cnblogs.com/jayxuan/p/18105597