# include <stdio.h>
# include <stdlib.h>
# include <string.h>
// 栈
typedef struct stack {
char data;
struct stack *next;
} StackAdder,*PStackAdder;
// 动态数组
typedef struct {
char *data; // 动态数组
int length; // 存储的有效数据
int maxlen; // 最大存储的有效数据
} Array,*PArray;
// 初始化栈
StackAdder *InitStack();
// 入栈
int Adder(StackAdder **Top,StackAdder **LastTop,StackAdder *Bottom,char data);
// 出栈
int Pop(StackAdder **Top,StackAdder **LastTop,StackAdder *Bottom,char *data);
// 获取栈顶指针
StackAdder *GetTop(StackAdder *Bottom,StackAdder **SLastTop);
// 空栈
int IsEmpty(StackAdder *Top,StackAdder *Bottom);
// 初始化动态数据
int InitArray(Array *arr,int n);
// 动态添加数组数据
Array ArrayAppend(Array *arr,char *v);
int strToNum(char c);
double Calculator(double i,double j,char x);
double toCal(char *formula) {
// 动态数组
Array aa;
InitArray(&aa,3);
// 2
// 1
// bottom 1 2
// 3 + 2 / (2 + 3) = 1
// 3 + 2 / 2 + 3 = 7
// 压栈，出栈
// 运算优先级: 1.[()] 2.[/ *] 3.[+ -]
// 栈初始化
PStackAdder SBottom;
PStackAdder STop;
PStackAdder SLastTop;
SBottom = InitStack();
STop = GetTop(SBottom,&SLastTop);
// 表达式，自动过滤 除 0-9 +-*/() 外的所有字符
//char formula[] = "9+(3-1)*3+1/2";
//char formula[] = "1+2-3*4/5+6";
int i;
char datas;
int OpCount = 0;
for (i=0;formula[i]!='\0';i++) {
// 判断为数字
if (('0' <= formula[i]) && ('9' >= formula[i])) {
datas = formula[i];
aa = ArrayAppend(&aa,&datas);
}
// 判断为操作符 + - * / ( )
if (('*' == formula[i]) || ('/' == formula[i]) || ('(' == formula[i]) || (')' == formula[i]) || ('+' == formula[i]) || ('-' == formula[i]) ) {
// + - * / 符号计数
if (('(' != formula[i]) && (')' != formula[i])) {
OpCount++;
}
// 为空，直接压栈
if(IsEmpty(STop,SBottom)) {
Adder(&STop,&SLastTop,SBottom,formula[i]);
continue;
}
switch(formula[i]) {
case '(': {
Adder(&STop,&SLastTop,SBottom,formula[i]);
break;
}
// 检测为 ) ,需要将 ) 至 ( 之间的符号全部出栈
case ')': {
while ('(' != STop->data) {
if (Pop(&STop,&SLastTop,SBottom,&datas)) {
aa = ArrayAppend(&aa,&datas);
}
}
// 丢弃 )
Pop(&STop,&SLastTop,SBottom,&datas);
break;
}
// 判断栈顶元素是否为 * / , 需要先出栈，然后入栈
case '*':
case '/': {
while (('*' == STop->data) || ('/' == STop->data)) {
Pop(&STop,&SLastTop,SBottom,&datas);
aa = ArrayAppend(&aa,&datas);
}
Adder(&STop,&SLastTop,SBottom,formula[i]);
break;
}
case '+':
case '-': {
// 判断为 * / 需要将栈清空,再压栈 + -
if (('*' == STop->data) || ('/' == STop->data)) {
while(Pop(&STop,&SLastTop,SBottom,&datas)) {
aa = ArrayAppend(&aa,&datas);
}
Adder(&STop,&SLastTop,SBottom,formula[i]);
} else {
Adder(&STop,&SLastTop,SBottom,formula[i]);
}
break;
}
}
}
}
while (STop != SBottom) {
if (Pop(&STop,&SLastTop,SBottom,&datas)) {
aa = ArrayAppend(&aa,&datas);
}
}
// 判断表达式
if ( (0 == aa.length%2) || (OpCount != (aa.length/2))) {
printf("表达式无法识别: %s\n",formula);
return -1;
}
char SuffixFormula[aa.length+1];
memcpy(&SuffixFormula,aa.data,sizeof(char) * aa.length);
SuffixFormula[aa.length] = '\0';
/*printf("\t");
for (i=0;i<aa.length;i++) {
printf("%c",aa.data[i]);
}
printf("\t");
*/
double StackCal[aa.length];
int StackTop = 0;
for (i=0;i<aa.length;i++) {
if (('0' <= aa.data[i]) && ('9' >= aa.data[i])) {
StackCal[StackTop] = (double)strToNum(aa.data[i]);
StackTop++;
} else {
double n = StackCal[StackTop-1];
double m = StackCal[StackTop-2];
double temp = Calculator(m,n,aa.data[i]);
StackTop = StackTop - 2;
StackCal[StackTop] = temp;
StackTop++;
}
}
printf("算法式:%s\t 后缀表达式:%s\t 计算结果: %.2lf\n",formula,SuffixFormula,StackCal[0]);
return StackCal[0];
}
int main() {
while (1) {
char formula[100];
printf("\n请输入10以内的表达式(不支持负数/不支持超过100的式子)\n：");
scanf("%s",formula);
printf("您输入的是: %s\n",formula);
double xx = toCal(formula);
printf("结果: %.2f\n",xx);
}
return 0;
}
// 加减乘除 运算符操作
double Calculator(double i,double j,char x){
switch (x) {
case '*':
return i*j;
case '/':
return i/j;
case '+':
return i+j;
case '-':
return i-j;
}
}
// 字符串转换为数字
int strToNum(char c) {
if (('0' <= c) && ('9' >= c)) {
return (c-48);
}
return 0;
}
// 初始化栈，使栈顶 指向 栈尾
StackAdder *InitStack() {
StackAdder * Bottom = (StackAdder *)malloc(sizeof(StackAdder));
if (NULL == Bottom) {
return NULL;
}
return Bottom;
}
// 出栈
int Pop(StackAdder **Top,StackAdder **LastTop,StackAdder *Bottom,char *data) {
if ((NULL == (*Top)) || (NULL == Bottom)) {
return 0;
}
if ((*Top) == Bottom) {
return 0;
}
//printf("%c\t",(*Top)->data);
*data = (*Top)->data;
//memcpy(data,&(*Top)->data,sizeof(char));
(*LastTop)->next = NULL;
free(*Top);
(*Top) = GetTop(Bottom,&(*LastTop));
return 1;
}
// 压栈
int Adder(StackAdder **Top,StackAdder **LastTop,StackAdder *Bottom,char data) {
if (NULL == Bottom) {
return 0;
}
StackAdder *newData = (StackAdder *)malloc(sizeof(StackAdder));
if (NULL == newData) {
printf("压栈失败,申请内存失败\n");
return 0;
}
newData->next = NULL;
newData->data = data;
(*Top)->next = newData;
(*LastTop) = (*Top);
*Top = newData;
return 1;
}
// 获取栈顶指针
StackAdder *GetTop(StackAdder *Bottom,StackAdder **LastTop) {
if (NULL == Bottom) {
return NULL;
}
PStackAdder Top = Bottom;
while (NULL != Top->next) {
*LastTop = Top;
Top = Top->next;
}
return Top;
}
// 栈为空返回1 否则返回0
int IsEmpty(StackAdder *Top,StackAdder *Bottom) {
if ((NULL == Top) && (NULL == Bottom)) {
return 0;
}
if (Top == Bottom) {
return 1;
}
return 0;
}
// 初始化动态数组
int InitArray(Array *arr,int n) {
if (NULL == arr) {
return 0;
}
arr->length = 0;
arr->maxlen = 0;
if (0 >= n) {
n = 1;
}
arr->data = (char *)malloc(sizeof(char) * n);
arr->maxlen = n;
return 1;
}
// 动态添加数组数据
Array ArrayAppend(Array *arr,char *v) {
if (arr->length+1 <= arr->maxlen) {
// 直接存储
memcpy(&arr->data[arr->length],v,sizeof(char));
//arr->data[arr->length] = *v;
arr->length = arr->length + 1;
return *arr;
} else {
// 重新申请内存再存储
Array tmp;
int Maxlen;
if (10 > arr->maxlen) {
Maxlen = (arr->maxlen) * 2;
} else {
Maxlen = (arr->maxlen) + (arr->maxlen / 2);
}
InitArray(&tmp,Maxlen);
// 将原有数据拷贝新数组中
// 方法1
memcpy(tmp.data,arr->data,sizeof(char) * arr->length);
// 方法2
//strcpy(tmp.data,arr->data);
// 方法3
//int i;
//for (i=0;i<arr->length;i++) {
// tmp.data[i] = arr->data[i];
//}
tmp.length = arr->length;
// 释放原有数据
free(arr->data);
// 递归调用存储
ArrayAppend(&tmp,v);
return tmp;
}
}
