表达式求值

Question

中缀表达式转换为后缀表达式，并求值，（C语言）
谢谢了！急求

Answer 1

从算法来说，要考虑中缀的运算符优先级，括号等，可以使用简单语法制导翻译，去看编译原理书吧，从数据结构来说，可以使用二元树和栈。使用二元树就是先建立表达式的树，然后后根遍历即可。难点在建立树。
使用栈的算法也很多，说个好想的。假设表达式的字符来自输入流in，建立栈A存放运算符，B存放结果，从in读入一个操作数压进B，读入一个运算符压进A，如此反复。
1.读入一个元素e
2.如果e是操作数或者(，压入B，跳转到1
3.如果e是运算符(不包含括号)，跳转到3.1
4.如果e是)，跳转到4.1
5.如果e是EOF，即输入流结束，反复弹出A栈顶压入B，直到A为空，算法结束，B从栈底到栈顶的符号即为后缀表达式（需要把B翻个个儿^_^）

3.1.判断A的栈定符号t，如果t不为(，且优先级大于等于e，则弹出t压入B，跳转到4，如果t为空，即栈中为空，或其他情况直接把e压入A，跳转到1
4.1.弹出A的栈顶压入到B，如此反复直到弹出的符号为(,(和)不要压入B,跳转到1

这是我临时想的，可能还有bug，或描述不清的地方，如果上网搜的话应该有很多源代码的，如果学过编译原理的话还可以有更好的算法，这个算法没考虑容错性。

Answer 2

建议看《数据结构》中关于栈的实现部分即可解决。

Answer 3

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAXNUM 100
typedef int DataType;
struct SeqStack
{
DataType s[MAXNUM];
int t;
};
typedef struct SeqStack *PSeqStack;
PSeqStack createEmptyStack_seq()
{
PSeqStack pastack;
pastack=(PSeqStack)malloc(sizeof(struct SeqStack));
if (pastack==NULL)
{
printf("Out of space!!\n");
}
else
{
pastack->t=-1;
}
return pastack;
}
int isEmptyStack_seq(PSeqStack pastack)
{
return pastack->t==-1;
}
void push_seq(PSeqStack pastack, DataType x)
{
if (pastack->t >= MAXNUM - 1)
printf("Overflow!\n");
else
{
pastack->t = pastack->t+1;
pastack->s[pastack->t]=x;
}
}
void pop_seq(PSeqStack pastack)
{
if (pastack->t==-1)
{
printf("Underflow!\n");
}
else
{
pastack->t = pastack->t-1;
}
}
DataType top_seq(PSeqStack pastack)
{
return pastack->s[pastack->t];
}
int infixtoSuffix(const char* infix, char* suffix)
{ /*将中缀表达式转换为后缀表达式，顺利转换返回true，若转换过程中发现中缀表达式非法则返回false*/
int state_int = FALSE;
/*state_int记录状态，等于true表示刚读入的是数字字符，等于false表示刚读入的不是数字字符，
设置这个变量是为了在每输出一个整数后输出一个空格，以免连续输出的两个整数混在一起。*/
char c, c2;
PSeqStack ps = createEmptyStack_seq(); /*运算符栈*/
int i, j = 0;
if(infix[0]=='\0')
{
return FALSE; /*不允许出现空表达式*/
}
for(i=0; infix[i]!='\0';i++)
{
c=infix[i];
switch(c)
{
case ' ':
case '\t':
case '\n':
if(state_int== TRUE)
{
suffix[j++]=' ';/*状态从true转换为false时输出一个空格*/
}
state_int= FALSE;
break; /*遇到空格或制表符忽略*/
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
state_int =TRUE;
suffix[j++]=c; /*遇到数字输出*/
break;
case '(':
if(state_int==TRUE)
{
suffix[j++]=' ';/*状态从true转换为false时输出一个空格*/
}
state_int=FALSE;
push_seq(ps, c); /*遇到左括号，入栈*/
break;
case ')':
if(state_int== TRUE)
{
suffix[j++]=' ';/*状态从true转换为false时输出一个空格*/
}
state_int=FALSE;
c2 = ')';
while(!isEmptyStack_seq(ps))
{
c2=top_seq(ps);/*取栈顶*/
pop_seq(ps); /*出栈*/
if(c2 =='(')
{
break;
}
suffix[j++]=c2;
}
if(c2 !='(')
{
free(ps);
suffix[j++]='\0';
return FALSE;
}
break;
case '+':
case '-':
if(state_int == TRUE)
{
suffix[j++] = ' ';
}
state_int = FALSE;
while(!isEmptyStack_seq(ps))
{
c2 = top_seq(ps);
if(c2 =='+'|| c2 =='-'|| c2 == '*' || c2 == '/')
{
pop_seq(ps);
suffix[j++] = c2;
}
else if(c2=='(')
{
break;
}
}
push_seq(ps, c);
break;
case '*':
case '/':
if(state_int==TRUE)
{
suffix[j++] = ' ';
}
state_int = FALSE;
while(!isEmptyStack_seq(ps))
{
c2 = top_seq(ps);
if(c2 == '*' || c2 == '/')
{
pop_seq(ps);
suffix[j++] = c2;
}
else if(c2=='+'||c2=='-'||c2=='(')
{
break;
}
}
push_seq(ps, c);
break;
default:
free(ps);
suffix[j++] = '\0';
return FALSE;
}
}
if(state_int == TRUE)
{
suffix[j++] = ' ';
}
while(!isEmptyStack_seq(ps))
{
c2 = top_seq(ps);
pop_seq(ps);
if(c2 == '(')
{
free(ps);
suffix[j++] = '\0';
return FALSE;
}
suffix[j++] = c2;
}
free(ps);
suffix[j++] = '\0';
return TRUE;
}
int calculateSuffix(const char * suffix, int * presult)
{

int state_int = FALSE;
PSeqStack ps = createEmptyStack_seq();
int num = 0, num1, num2;
int i;
char c;
for(i = 0; suffix[i] != '\0'; i++)
{
c = suffix[i];
switch(c)
{
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
if(state_int == TRUE)
{
num = num * 10 + c - '0';
}
else
{
num = c - '0';
}
state_int = TRUE;
break;
case ' ':
case'\t':
case '\n':
if (state_int == TRUE)
{
push_seq(ps, num);
state_int = FALSE;
}
break;
case '+':
case '-':
case '*':
case '/':
if(state_int == TRUE)
{
push_seq(ps, num);
state_int = FALSE;
}
if(isEmptyStack_seq(ps))
{
free(ps);
return FALSE;
}
num2 = top_seq(ps);
pop_seq(ps);
if(isEmptyStack_seq(ps))
{
free(ps);
return FALSE;
}
num1 = top_seq(ps);
pop_seq(ps);
if(c == '+')
{
push_seq(ps, num1 + num2);
}
if(c == '-')
{
push_seq(ps, num1 - num2);
}
if(c == '*')
{
push_seq(ps, num1 * num2);
}
if(c == '/')
{
push_seq(ps, num1 / num2);
}
break;
default:
free(ps);
return FALSE;
}
}
*presult = top_seq(ps);
pop_seq(ps);
if(!isEmptyStack_seq(ps))
{
free(ps);
return FALSE;
}
free(ps);
return TRUE;
}
void getline(char* line, int limit)
{
char c;
int i=0;
while(i<limit-1&&(c = getchar())!=EOF&&c!='\n')
{
line[i++]=c;
}
line[i]='\0';
}
int main()
{
char c, infix[MAXNUM], suffix[MAXNUM];
int result;
int flag = TRUE;
while(flag == TRUE)
{
printf("Plese input an infix expression!\nInput:");
getline(infix, MAXNUM);
if(infixtoSuffix(infix, suffix) == TRUE)
{
printf("suffix:%s\n", suffix);
}
else
{
printf("Invalid infix!\n");
printf("\nContinue? (y/n)");
scanf("%c", &c);
if(c == 'n' || c == 'N')
{
flag = FALSE;
}
while(getchar() != '\n');
{
printf("\n");
}
continue;
}
if(calculateSuffix(suffix, &result) == TRUE)
{
printf("Result:%d\n", result);
}
else
{
printf("Invalid suffix!\n");
}
printf("\nContinue? (y/n)");
scanf("%c", &c);
if(c == 'n' || c == 'N')
{
flag = FALSE;
}
while(getchar() != '\n');
{
printf("\n");
}
}
}

参考资料：hi.baidu.com/lookforabetterplace_zcci123