数据结构与算法题目集7-20——表达式转换
我的数据结构与算法题目集代码仓:https://github.com/617076674/Data-structure-and-algorithm-topic-set
原题链接:https://pintia.cn/problem-sets/15/problems/827
题目描述:
知识点:中缀表达式转后缀表达式
思路:利用栈将中缀表达式转换为后缀表达式
将中缀表达式转化为后缀表达式的规则:
从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即成为后缀表达式的一部分;若是符号,则判断其与栈顶符号的优先级,是右括号或优先级不高于栈顶符号则栈顶元素依次出栈并输出,并将当前符号进栈,一直到最终输出后缀表达式为止。
本题的难点在于如何区分数字和符号,题给的数字可能是小数,也可能是带负号的负数,也可能是带正号的正数。
时间复杂度和空间复杂度均是O(N),其中N为所给字符串的长度。
给出本题各个测试点的测试数据:
序号 | 输入 | 输出 | 说明 |
0 | 2+3*(7-4)+8/4 | 2 3 7 4 - * + 8 4 / + | 正常测试6种运算符 |
1 | ((2+3)*4-(8+2))/5 | 2 3 + 4 * 8 2 + - 5 / | 嵌套括号 |
2 | 1314+25.5*12 | 1314 25.5 12 * + | 运算数超过1位整数且有非整数出现 |
3 | -2*(+3) | -2 3 * | 运算数前有正负号 |
4 | 123 | 123 | 只有一个数字 |
C++代码:
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
bool isDigit(char c);
bool isPositiveOrNegative(char c);
bool isTimeForPoping(char c1, char c2);
int main() {
char input[21];
scanf("%s", input);
bool space = false; //用来标记是否需要输出空格
stack<char> Stack;
for(int i = 0; i < strlen(input); i++) {
char c = input[i];
if(isDigit(c)) {
if(space) {
printf(" ");
space = false;
}
printf("%c", c);
//首位的正负号肯定不是运算符
//对于不是首位的正负号,i - 1位置既不是数字也不是')'的肯定不是运算符
} else if(isPositiveOrNegative(c) && ((i == 0) || (!isDigit(input[i - 1]) && input[i - 1] != ')'))) {
if(c == '-') {
if(space) {
printf(" ");
space = false;
}
printf("%c", c);
}
} else {
if(!Stack.empty()) {
if(c == ')')
while(!Stack.empty()) {
char top = Stack.top();
Stack.pop();
if(top == '(') {
break;
}
printf(" %c", top);
}
else {
while(!Stack.empty()) {
char top = Stack.top();
if(isTimeForPoping(top, c)) {
printf(" %c", top);
Stack.pop();
} else {
break;
}
}
Stack.push(c);
}
} else {
Stack.push(c);
}
stack<char> Stack2;
while(!Stack.empty()){
Stack2.push(Stack.top());
if(Stack.top() != '('){
space = true; //如果此时栈中包含'('外的其他符号,space需要置为true
}
Stack.pop();
}
while(!Stack2.empty()){
Stack.push(Stack2.top());
Stack2.pop();
}
}
}
while(!Stack.empty()) {
printf(" %c", Stack.top());
Stack.pop();
}
return 0;
}
bool isDigit(char c) {
if(c >= '0' && c <= '9') {
return true;
} else if(c == '.') {
return true;
}
return false;
}
bool isPositiveOrNegative(char c) {
if(c == '+' || c == '-') {
return true;
}
return false;
}
bool isTimeForPoping(char c1, char c2) {
if(c2 == ')') {
return true;
} else if(c1 == '(' || c2 == '(') {
return false;
} else if(c2 == '+' || c2 == '-') {
return true;
} else if(c2 == '*' || c2 == '/') {
if(c1 == '+' || c1 == '-') {
return false;
} else if(c1 == '*' || c1 == '/') {
return true;
}
}
}
C++解题报告: