逆波兰表达式c语言
❶ 将下面的算术运算式表示成逆波兰式（数据结构 c语言版）
a*b*c → **abc
a*b*c+c*d → +**abc*cd
(a+b)*((c-d)*e+f) → *+ab+*-cdef
上面是波兰式，逆波兰式如下：
a*b*c → ab*c*
a*b*c+c*d → ab*c*cd*+
(a+b)*((c-d)*e+f) → ab+cd-e*f+*
写出(a+b)*((c-d)*e+f)转换时栈的变化情况：【注意，右端为栈顶】
读入（，入栈，栈中为（，输出：（空）；
读入a，直接输出，栈中为（，输出：a；
读入+，入栈，栈中为（+，输出：a；
读入b，直接输出，栈中为（+，输出：ab；
读入），依次推出栈中的符号，直到遇见一个（【注意括号不输出】，栈中为空，输出：ab+；
读入*，入栈，栈中为*，输出：ab+；
读入（，入栈，栈中为*（，输出：ab+；
读入（，入栈，栈中为*（（，输出：ab+；
读入c，直接输出，栈中为*（（，输出：ab+c；
读入-，入栈，栈中为*（（-，输出：ab+c；
读入d，直接输出，栈中为*（（-，输出：ab+cd；
读入），依次推出栈中的符号，直到遇见一个（【注意括号不输出】，栈中为*（，输出：ab+cd-；
读入*，入栈，栈中为*（*，输出：ab+cd-；
读入e，直接输出，栈中为*（*，输出：ab+cd-e；
读入+，【由于此时栈中的*的优先级高于+，所以先将*退栈，然后+入栈】，栈中为*（+，输出：ab+cd-e*；
读入f，直接输出，栈中为*（+，输出：ab+cd-e*f；
读入），依次推出栈中的符号，直到遇见一个（【注意括号不输出】，栈中为*，输出：ab+cd-e*f+；
此时读入已经完毕，栈中还剩一个*，输出：ab+cd-e*f+*
完毕！
以上就是整个从中缀表达式到后缀表达式的过程，栈的变化情况已经都写出来了。
❷ C语言 逆波兰表达式 算法
#include <stdio.h>
#include <string.h>
int main()
{
double d[100], *dp = d;
int m, k;
char t[50], *tp = t;
char s[100], *c = s;
char* op = "+-*/";
char* fg = "0123456789.";
gets(s);
while(*c) {
if(strchr(op, *c)) {
*tp++ = *c;
k = 0;
}else
if(strchr(fg, *c)) {
sscanf(c, "%lf%n", dp++, &m);
c += m - 1;
++k;
}
++c;
while((dp - d > 1 && k == 2) || !*c && dp - d >= 1) {
switch(*--tp) {
case '+': dp[-2] = dp[-2] + dp[-1]; break;
case '-': dp[-2] = dp[-2] - dp[-1]; break;
case '*': dp[-2] = dp[-2] * dp[-1]; break;
case '/': dp[-2] = dp[-2] / dp[-1]; break;
}
--dp;
}
}
printf("%f", *dp);
}
❸ 算术表达式转化成逆波兰式（C语言）
你可以扩展一下。
// 中缀表达式转化为后缀表达式，仅支持加减乘除运算、操作数为1位十进制非负整数的表达式。
char* infix2postfix(const char *infix, char *postfix)
{
const size_t N = strlen(infix);
if (N == 0 || postfix == NULL)
{
return postfix;
}
stack<char> opcode(N); // 堆栈存放的是操作符
for (size_t i = 0; i < N; i++)
{
switch (infix[i])
{
case '(': // 直接忽略左括号
break;
case ')': // 弹出操作符
*postfix++ = opcode.pop();
*postfix++ = ' ';
break;
case '+':
case '-':
case '*':
case '/':
opcode.push(infix[i]); // 压入操作符
break;
default:
if (isdigit(infix[i])) // 如果是数字，直接输出
{
*postfix++ = infix[i];
*postfix++ = ' ';
}
}
}
return postfix;
}
❹ C语言编写逆波兰计算器
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.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);
}
❺ 将一般算术表达式转化为逆波兰式（c语言）
内存引用错误，一般都是指针没有初始化。
你的指针sq，没有初始化，就引用了。呵呵。
=========================================
用指针需要malloc，或者指向一个局部变量。
干脆直接用变量吧，如tanyuguo所说，Sqstack sq;还要把后面的sq->全部改成sq.
此外，
第一个接受输入的循环不对。
用标准用法while。
whil((c = getchar()) != '#')
str[i] = c;
后面的代码没有看。
给你一个建议：每一步后面加上printf打印当前的一些结果，你就能一步一步调试了。否则，这么长的程序一次找到所有错误是不可能的。
❻ 用c语言的栈来编写逆波兰公式的程序
如题，代码如下，欢迎探讨！！！
[code=C/C++][/code]
/*
表达式的后缀表示及其求值
*/
#include
<stdio.h>
typedef
int
ElemType;
/*
考虑到char型运算时的隐形提升会溢出，此处定义为int，代价仅浪费了内存空间
*/
#define
MAXNUM
16
struct
stack
{
ElemType
data[MAXNUM];
int
top;
};
void
StackInit(struct
stack
*stack)
{
int
i
=
0;
for(;i
<
MAXNUM;i++)
{
stack->data[i]
=
0;
}
stack->top
=
0;
/*
栈底部从索引0处开始
*/
}
void
StackPush(struct
stack
*stack,ElemType
c)
{
if(MAXNUM
==
stack->top)
/*
栈中元素最多有MAXNUM
-
1个
*/
{
printf("The
stack
is
full
");
return;
}
stack->data[stack->top++]
=
c;
}
ElemType
StackPop(struct
stack
*stack)
{
if(0
==
stack->top)
{
printf("The
stack
is
empty
");
/*
当栈空时，若返回0是错误的
*/
return
0;
}
return
stack->data[--stack->top];
}
void
PostfixEvaluation(struct
stack
*stack)
{
return;
/*
这个函数非常简单了，所有的麻烦都已经解决了，我实在不想完成它
*/
}
int
ChangeToPostfix(char
*str)
{
int
i
=
0,flag
=
0;
/*
flag
用来标记连续数字的出现，没想到好点的办法
*/
int
c,ch;
struct
stack
ch_stack;
struct
stack
op_stack;
StackInit(&ch_stack);
StackInit(&op_stack);
while(
!=
(c
=
*(str
+
i)))
/*
此处需注意的是:如果是静态的字符串，以为结束条件,如果是用户输入的，则以
’为结束条件
*/
{
if((*
==
c)
||
(/
==
c)
||
((
==
c))
{
flag
=
0;
StackPush(&op_stack,c);
}
else
if()
==
c)
{
flag
=
0;
while((
!=
(c
=
StackPop(&op_stack)))
{
StackPush(&ch_stack,c);
}
if(0
==
op_stack.top)
{
printf("the
(
hasnt
found
when
the
)
come
in!
");
return
-1;
}
}
else
if((+
==
c)||
(-
==
c))
{
flag
=
0;
/*
+和-优先级低，运算符栈中的((如果存在)后的所有运算符需推出
*/
if(0
!=
op_stack.top)
/*
你可以不在此处添加top的检查，那样，你可以发现
StackPop错误返回的0被拾取了
*/
{
/*
被逼无奈,只得在此检查top值，无法寄希望于StackPop了
*/
while((
!=
(ch
=
StackPop(&op_stack)))
{
StackPush(&ch_stack,ch);
if(0
==
op_stack.top)
{
break;
}
}
}
StackPush(&op_stack,c);
}
else
if((c
>=
0)
&&
(c
<=
9))
/*
对于表达式中2位或多位连续的数字，需特殊处理
*/
{
if(0
==
flag)
{
StackPush(&ch_stack,(c
-
0));
flag
=
1;
}
else
{
StackPush(&ch_stack,10
*
StackPop(&ch_stack)
+
(c
-
0));
}
}
i++;
}
while(0
!=
op_stack.top)
/*
表达式处理结束，将运算符栈中的所有运算符推出并压入字符栈
*/
{
StackPush(&ch_stack,StackPop(&op_stack));
}
PostfixEvaluation(&ch_stack);
/*
该函数放在此处可能较为欠妥，可是，只要完成了任务不就OK了么，难道你会在乎？
*/
/*just
test
*/
for(i
=
0;i
<
ch_stack.top;i++)
{
if(+
==
ch_stack.data[i])
{
printf("+..");
}
else
if(-
==
ch_stack.data[i])
{
printf("-..");
}
else
if(*
==
ch_stack.data[i])
{
printf("*..");
}
else
if(/
==
ch_stack.data[i])
{
printf("/..");
}
else
{
printf("%d..",ch_stack.data[i]);
}
}
return
0;
}
int
main(void)
{
char
str[]
=
"12
+
34
*
435
-
5
/
1";
/*
just
test
*/
printf("The
result
should
be
:
");
printf("12
34
435
*
+
5
1
/
-
[=
8]
");
if(-1
==
ChangeToPostfix(str))
{
printf("ChangeToPostfix()
error
");
return
1;
}
return
0;
}
❼ C语言中有表达式，逆波兰二词，何为表达式，何为逆波兰，谁能告诉我一下，谢谢啦
运算符置于其运算对象之后，这种表达式就是逆波兰表达式。如：a=1+3 ---> a=1,3 +
❽ 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;i<n;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;i<m;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;i<m;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语言求解逆波兰表达式
使用栈完成
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下运行正确 希望对你有帮助
#include<stdio.h>
#include<string.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();
}