#include <stdio.h>
#include<Windows.h>
#define MaxSize 10
typedef struct {
char data[MaxSize];
int top;//栈顶指针
}SqStack;
void InitStack(SqStack *S) {
S->top = -1;
}
BOOL isEmpty(SqStack *s) {
if (s->top == -1) {
return TRUE;
}
}
void Push(SqStack *S, char x)
{
if (S->top == MaxSize - 1) {
printf("顺序栈已满,不允许再添加\n");
return -1;
}
S->data[++S->top] = x;
}
char Pop(SqStack *S)
{
if (S->top == -1) {
printf("栈已空");
return -1;
}
char x = S->data[S->top--];
return x;
}
//中缀表达式转后缀表达式
void ConcluseExpression(char str[], int length) {
SqStack S;
InitStack(&S);
int i = 0;
char *str_1 = (char*)malloc(sizeof(char));
int m = 0;
int count = 0;
int tag = 0;
int tag_2 = 0;
int tag_3 = 0;
for (i = 0; i < length; i++) {
if (str[i] != '*' && str[i] != '/' && str[i] != '+' && str[i] != '-'&&str[i] != '('&&str[i] != ')') {
str_1[m++] = str[i];
}
if (str[i] == '*' || str[i] == '/' || str[i] == '+' || str[i] == '-') {
Push(&S, str[i]);
}
if (str[i] == '(') {
tag_2++;
if (tag_2 == 1) tag_3 = i;
if (str[i + 1] == '(') {
tag = 1;
continue;
}
else {
if (str[i + 1] == '*' || str[i + 1] == '/' || str[i + 1] == '+' || str[i + 1] == '-' || str[i + 1] == ')') {
printf("错误:中缀表达式输入错误");
return -1;
}
int k = 0;
count = i + 1;
for (k = i + 1; str[i + 1] != ')'&&str[i + 1] != '('; k++, i++) {
if (str[k] != '*' && str[k] != '/' && str[k] != '+' && str[k] != '-')
str_1[m++] = str[k];
else
Push(&S, str[k]);
}
}
}
if (str[i] == ')'&&tag == 1) {
if (str[i + 1] == ')') {
continue;
}
else {
if (str[i + 1] == '*' || str[i + 1] == '/' || str[i + 1] == '+' || str[i + 1] == '-') {
int n;
for (n = 0; str[count] != '+'&&str[count] != '-'
&&str[count] != '*'&&str[count] != '/'; n++, count++)
str_1[m++] = Pop(&S);
count = i;
if (str[i + 2] != '*'&&str[i + 2] != '/'&&str[i + 2] != '+'&&str[i + 2] != '-'&&str[i + 2] != '\0'&&
str[i + 2] != ')'&&str[i + 2] != '('&&str[i + 3] != '\0') {
str_1[m++] = str[i + 2];
Push(&S, str[i + 1]);
str_1[m++] = Pop(&S);
i = i + 2;
continue;
}
tag = 0;
continue;
//Push(&S,str[i+1]);
}
if (str[i + 1] == '\0') {
break;
}
else {
printf("错误:输入的c语句不合法!\n");
return -1;
}
}
}
if (str[i] == ')'&&tag == 0) {
if (str[i + 1] == ')') {
continue;
}
else {
if (str[i + 1] == '*' || str[i + 1] == '/' || str[i + 1] == '+' || str[i + 1] == '-') {
int n;
if (str[tag_3 - 1] == '+' || str[tag_3 - 1] == '-') {
for (n = 0; str[count] != ')'; n++, count++)
str_1[m++] = Pop(&S);
continue;
}
if (str[tag_3 - 1] == '*' || str[tag_3 - 1] == '/') {
for (n = 0; str[count - 1] != ')'; n++, count++)
str_1[m++] = Pop(&S);
continue;
}
}
if (str[i + 1] == '\0') {
break;
}
else {
printf("错误:输入的c语句不合法!\n");
return -1;
}
}
}
}
int lengthofStr_1 = m;
while (isEmpty(&S) != TRUE) {
str_1[m++] = Pop(&S);
}
int j;
for (j = m - 1; j > lengthofStr_1; j--) {
if ((str_1[j] == '*'&&str[j - 1] == '+') || (str_1[j] == '*'&&str[j - 1] == '-')
|| (str_1[j] == '/'&&str[j - 1] == '+') || (str_1[j] == '/'&&str[j - 1] == '-'))
{
char temp = str_1[j];
str_1[j] = str_1[j - 1];
str_1[j - 1] = temp;
}
}
int k;
printf("其后缀表达式为:\n");
for (k = 0; k < m; k++) {
printf("%c ", str_1[k]);
}
printf("\n");
}
int main() {
char *str = (char*)malloc(sizeof(char));
printf("输入中缀表达式:\n");
scanf("%s", str);
int length = 0;
while (str[length] != '\0')
length++;
ConcluseExpression(str, length);
}