您的位置:

c语言用递归求逆波兰,c语言实现逆波兰式

本文目录一览:

C语言 逆波兰表达式

这个问题可以分为3部分

1、输入一个字符串,将其格式化的储存在一个数组中,以方便的记录表达式中数和各个符号的出现顺序

约定在数组中记录时,每个数或符号用两个整数来记录

第一个整数记录该位是什么东西,0表示是一个数,1表示是括号,2表示反括号,3、4、5、6分别表示乘除加减号

如果该位是一个数,那么第二个整数记录着个数的具体取值,否则记录该位的符号的ASCII码

比如字符串"(1-23)"会被转化成二位数组 , , , , }

这个转化过程每什么技巧性,对原字符串各位顺次判断并处理即可

原先的字符串中可能出现一元运算符正号'+'和负号'-',为了处理方便,一律在其前面加个0,改写成"0+..."或者"0-..."

另外为了之后转化逆波兰表达式方便,处理过程中会在转化出的数组的首尾一律添加一对括号

2、将之前所提到的格式数组转化为逆波兰表达式

约定依然用二位数组记录一个逆波兰表达式,并且格式与之前的数组相同,除了没有括号以外

比如逆波兰表达式 1 2 - 35 +,会被记录成{ , , , , }

转化时,需要用一个栈

具体转化操作如下:

顺次处理格式数组的每一位,对其作判断

如果该位是一个数或者是括号'(',,将其入栈

如果该位是乘号'*'或者除号'/',不断进行出栈操作直到栈顶元素是个括号'('或者加号'+'或者减号'-',然后将这个乘号或者除号入栈

如果该位是加号'+'或者减号'-',不断进行出栈操作直到栈顶元素是个括号'(',然后将这个加号或者减号入栈

如果该位是反括号')',那么不断进行出栈操作直到有一个括号'('出栈

在上述操作中,所有的出栈元素,除了括号'('以外,都被顺次添加到所要生成的逆波兰表达式的末尾

这样就转化出了一条逆波兰表达式

3、对逆波兰表达式求值

求值时,也需要用到一个栈

求值步骤如下:

顺次处理逆波兰表达式的每一位,对其作判断

如果该位是一个数,将这个数入栈

如果该位是一个运算符,那么连续进行两次出栈操作,可以得到栈顶的两个元素,对这两个元素用该位的运算符做运算,将所得的结果入栈

比如,如果当时栈顶元素是3,次栈顶的元素是2,运算符是减号'-',那么连续两次出栈得到3和2两个元素,再将2-3的运算结果1入栈

注意有些运算符(减号和除号)不符合交换律,因此运算时必须是次栈顶元素在前、栈顶元素在后,顺序不能反

当每一位都处理完了之后,只要输入的是一个合法的逆波兰表达式,必然栈中只剩下一个元素,这个元素就是逆波兰表达式求值的结果

源代码如下:

#include stdio.h

#include ctype.h

void transform(char *str,int a[][2],int *n)

//将输入的字符串转化为格式化的数组以记录输入的表达式,str为输入的字符串,a为目标数组,n记录数组a的大小

{

int i;

*n=1;

a[0][0]=1;

a[0][1]='(';//在表达式首添加一个括号

for (i=0;str[i];)

{

if (isdigit(str[i]))

{

a[*n][0]=0;

a[*n][1]=0;

while (isdigit(str[i]))

{

a[*n][1]=a[*n][1]*10+str[i]-'0';

i++;

}

}

else

{

if (str[i]=='(') a[*n][0]=1;

else if (str[i]==')') a[*n][0]=2;

else if (str[i]=='*') a[*n][0]=3;

else if (str[i]=='/') a[*n][0]=4;

else if (str[i]=='+' || str[i]=='-')

{

if (i==0 || (!isdigit(str[i-1]) str[i-1]!=')'))

{

a[*n][0]=0;

a[*n][1]=0;

(*n)++;

}

if (str[i]=='+') a[*n][0]=5;

else a[*n][0]=6;

}

a[*n][1]=str[i];

i++;

}

(*n)++;

}

a[*n][0]=2;

a[*n][1]=')';//在表达式尾添加一个反括号

(*n)++;

}

void poland(int a[][2],int n,int p[][2],int *m)

//将格式化数组转化为逆波兰表达式,a为输入的数组,n为其长度,p为输出逆波兰表达式的目标,m记录逆波兰表达式的长度

{

int i;

int stack[1000];//转化所用的栈

int depth;//栈的深度

depth=0;

*m=0;

for (i=0;in;i++)

{

if (a[i][0]==0) stack[depth++]=i;

else if (a[i][0]==1) stack[depth++]=i;

else if (a[i][0]==2)

{

while (a[stack[depth-1]][0]!=1)

{

depth--;

p[*m][0]=a[stack[depth]][0];

p[*m][1]=a[stack[depth]][1];

(*m)++;

}

depth--;

}

else if (a[i][0]==3 || a[i][0]==4)

{

while (a[stack[depth-1]][0]==0 || a[stack[depth-1]][0]==3 || a[stack[depth-1]][0]==4)

{

depth--;

p[*m][0]=a[stack[depth]][0];

p[*m][1]=a[stack[depth]][1];

(*m)++;

}

stack[depth++]=i;

}

else if (a[i][0]==5 || a[i][0]==6)

{

while (a[stack[depth-1]][0]!=1)

{

depth--;

p[*m][0]=a[stack[depth]][0];

p[*m][1]=a[stack[depth]][1];

(*m)++;

}

stack[depth++]=i;

}

}

}

void print_poland(int p[][2],int m)

//打印逆波兰表达式,p为逆波兰表达式,m为表达式长度

{

int i;

for (i=0;im;i++)

{

if (p[i][0]==0) printf("%d",p[i][1]);

else printf("%c",p[i][1]);

}

putchar('\n');

}

double evaluate(int p[][2],int m)

//对逆波兰表达式求值,p为逆波兰表达式,m为表达式长度

{

double stack[1000];//求值所用的栈

int depth;//栈的深度

int i;

depth=0;

for (i=0;im;i++)

{

if (p[i][0]==0) stack[depth++]=p[i][1];

else

{

double a,b;

b=stack[--depth];

a=stack[--depth];

if (p[i][0]==3) stack[depth++]=a*b;

else if (p[i][0]==4) stack[depth++]=a/b;

else if (p[i][0]==5) stack[depth++]=a+b;

else stack[depth++]=a-b;

}

}

return stack[0];

}

int a[1000][2];

int n;

int p[1000][2];

int m;

main()

{

transform("5*(8-2)+9",a,n);

poland(a,n,p,m);

print_poland(p,m);

printf("The result of the expression is %lf\n",evaluate(p,m));

return;

}

逆波兰表达式求值 c++

这是典型的递归算法(这是前缀表达式吧)即在函数中调用函数本身第一层递归时接受输入字符(缓冲区10字符,第一个字符默认为0,防止不输入)并读取第一个字符。(总的来说就是为了读取单个运算符号或者一串数字列)若读取出为运算符号如'+'则在return时调用f()+f()这里有两次调用f(),每次调用f()时都需要请求你输入字符。这两次调用f()时,即进入了第二层递归。假定这里你两次输入了'1','2'那么对于第一层递归中的returnf()+f();其中第一个f()中返回了你的输入1,第二个则返回2此时回到第一层,在f()+f()时就运算出结果3最终退出第一层递归,回到main()输出前缀表达式的结果。如果更加复杂(输入了很多运算符),同样可以按照上面所说的这种思想来看。关于递归,一开始理解起来会有些困难,可以找些例子并且自己试验。

C语言编写逆波兰计算器

#includestdio.h

#includestdbool.h

#includestdlib.h

#defineSTACK_SIZE 20

intmake_empty(void);

boolis_empty(void);

boolis_full(void);

voidpush(char );

voidpop(char );

voidstack_overflow(void);

voidstack_underflow(void);

charcontents[STACK_SIZE]= {0},top;

intmain(int argc, char *argv[])

{

char ch='1';

while(ch!='q'){

make_empty();

printf("Enter an RPNexpression:");

do{

scanf(" %c",ch);

if(ch='1'ch='9')

push(ch);

else if(ch=='+'||ch=='-'||ch=='*'||ch=='/'){

top--;pop(ch);

}

else if(ch=='='){

if((top-1)==0)

pop(ch);

else

printf("Nunber notused!");

break;

}

else if(ch=='\n');

else{

ch='q';break; /*其它情况置为退出标志q*/

}

}

while(ch!='\n');

}

return 0;

}

intmake_empty(void){

/* return top=0;

}

boolis_empty(void){

return top==0;

}

boolis_full(void){

return top==STACK_SIZE;

}

voidpush(char ch){

if(is_full())

stack_overflow();

else

contents[top++]=ch-'0';

}

voidpop(char ch){

if(is_empty())

stack_underflow();

else

switch(ch){

case'+':contents[top-1]+=contents[top];break;

case '-':contents[top-1]-=contents[top];break;

case'*':contents[top-1]*=contents[top];break;

case'/':contents[top-1]/=contents[top];break;

case '=':printf("Value ofexpression:%d\n",(int)contents[0]);break;

}

}

voidstack_overflow(void){

printf("Expression is toocomplex!");

exit(EXIT_FAILURE);

}

voidstack_underflow(void){

printf("Not enough operands inexpression!");

exit(EXIT_FAILURE);

}

逆波兰表达式(递归)形成栈

不是,cin只是用来读取数据。

实际上这个程序巧妙地用了递归(底层原理是系统栈,有65000层)代替数据结构的栈,使程序代码更加简洁(但是在运算符超过65000个时系统栈可能会“爆栈”)。

C语言求解逆波兰表达式

使用栈完成

int add(char s[])

{

int st[100];

char *p;

int top=-1;

int A,B,sum=0;

for(p=s;*p!=0;p++)//进行数值计算

{

switch (*p)

{

case '0':

case '1':

case '2':

case '3':

case '4':

case '5':

case '6':

case '7':

case '8':

case '9':st[++top]=*p-'0';break;//是数字压入总栈st中

case '+':

case '-':

case '*':

case '/'://是运算符号

A=st[top--];

B=st[top--];//弹出2个数字

switch (*p)

{

case '+':sum=B+A;break;

case '-':sum=B-A;break;

case '*':sum=B*A;break;

case '/': sum=B/A;break;

}

st[++top]=sum;//将结果重新压入栈

break;

}

}

return sum;

}

C语言逆波兰算数表达式

我用c语言写的wintc下运行正确 希望对你有帮助

#includestdio.h

#includestring.h

int nibolan(char s[])

{ int i=0,a,b;

char *p;

p=s ;

while(*p!='\0')

{if(*p=='+'){*p=((*(p-2)-48)+(*(p-1)-48))+48;}

if(*p=='-'){*p=((*(p-2)-48)-(*(p-1)-48))+48;}

if(*p=='*'){*p=((*(p-2)-48)*(*(p-1)-48))+48;}

if(*p=='/'){*p=((*(p-2)-48)/(*(p-1)-48))+48;}

p++;

} p--;

return (*p)-48;

}

main()

{ int r;

char a[100];

gets(a);

r=nibolan(a);

printf("%d",r);

getch();

}