救命啊（5天有效）逆波兰 字符表达式的正逆输出（我要被逼疯了）！！！！
如有符号表达式：a＋b×(c－d)－e÷f
1、输入a＋b×(c－d)－e÷f
应输出a b c d － × ＋ e f ÷ －
2、输入a b c d － × ＋ e f ÷ －
应输出a＋b×(c－d)－e÷f
3、表要求判断输入是否正确，即：用不着你引用大量的编译原理理论来教育我^_^
4、需要输出的是表达式还是逆波兰式由人决定，即不需要代码判断
5、我搞了好久好久，也没把2搞出来，要加括号有点难哦
问题点数：100、回复次数：36Top
1 楼docong（欢聚悲散一杯酒，南北东西万里程）回复于 2005-06-04 16:19:13 得分 0
更正：3、表（表字写错了，应为“不”）要求判断输入是否正确，即：用不着你引用大量的编译原理理论来教育我^_^
3、不要求判断输入是否正确，即：用不着你引用大量的编译原理理论来教育我^_^
Top
2 楼newbiestar（）回复于 2005-06-04 16:25:18 得分 0
从中缀开始的是最讨厌的，到中缀的操作符优先级也是很讨厌的……Top
3 楼mccxj（老鼠不逛街）回复于 2005-06-04 16:25:58 得分 0
压栈。。优先级。。。。
3和4不是顺序的问题吗？。。up一下。。Top
4 楼mccxj（老鼠不逛街）回复于 2005-06-04 16:30:53 得分 0
输入a b c d － × ＋ e f ÷ －
应输出a＋b×(c－d)－e÷f
要先定义运算的优先数。。如加减为1，乘除为2
对于每一个输入。。用一个栈把它存起来。直到遇到运算符号。。。遇到符号时候从栈中取出数据。。如果在它前面的符合的优先级比它高。。就应该加扩号。。。。
类似这样的思路。。。Top
5 楼foochow（无聊,灌水......）回复于 2005-06-04 16:31:26 得分 80
我把收藏的发给你,忘了是论坛上那个大哥写的了-_-Top
6 楼foochow（无聊,灌水......）回复于 2005-06-04 16:32:02 得分 0
#include<iostream.h>
#include<string.h>
#include<math.h>
#include<ctype.h>
#define maxbuffer 64
void main()
{
char display_out(char out_ch[maxbuffer], char ch[32]);
//int caculate_array(char out_ch[32]);
static int i=0;
static int j=0;
char ch[maxbuffer],s[maxbuffer],out[maxbuffer];
cout<<"请输入中缀表达式: ";
cin>>ch;
for(i=0;i<maxbuffer;i++)
{out[i]=ch[i];}
cout<<"请确认您输入的表达式： ";
while(out[j]!='#')
{
cout<<out[j];
j++;
}
cout<<'#'<<endl;
display_out(s,out);
//caculate_array;
}
char display_out(char out_ch[32],char ch[])
{
int top=-1;
int i=0,data[maxbuffer],n;
int j=0;
char sta[20];
while(ch[i]!='#')
{
if(isalnum(ch[i]))
{
while(isalnum(ch[i]))
{
out_ch[j]=ch[i];
j++;
i++;
}out_ch[j]=' ';j++;
}
else{
switch(ch[i])
{
case '+':
case '-': if(sta[top]=='('||top==-1)
{
top++;
sta[top]=ch[i];
i++;
}
else
{
//j--;
out_ch[j]=sta[top];
j++;
top--;
//i++;
}
break;
//break;
case '*':
case '/':if(sta[top]=='*'&&sta[top]=='/')
{
out_ch[j]=sta[top];
j++;
//i++;
top--;
}
else
{
top++;
sta[top]=ch[i];
i++;
}
break ;
//break;
case '(':top++;
sta[top]=ch[i];
i++;
break;
case ')':if(sta[top]=='(')
{
top--;
i++;
}
if(top==-1)
{
cout<<"错误: 第"<<j<<"个位置的“)”没有找到与之匹配的“(”";
ch[i]='#';j=0;
}
else
{
//while(sta[top]!='('){
out_ch[j]=sta[top];
top--;
j++;
//}break;
}
break;
/*case '#': out_ch[j]='#';
j++;
break;*/
default:
cout<<" your input is error"<<endl;
ch[i]='#';
j=0;
break;
}
}
}while(top!=-1)
{
out_ch[j]=sta[top];j++;
top--;
}
out_ch[j]='#';
n=0;
cout<<"逆波兰表达式为: ";
while(out_ch[n]!='#')
{
cout<<out_ch[n];
n++;
}
cout<<endl;
j=0;
/*while(ch[j]!='#')
{
top++;
data[top]=ch[j];
}
cout<<data[top];
*/
return out_ch[maxbuffer];
}Top
7 楼foochow（无聊,灌水......）回复于 2005-06-04 16:35:51 得分 0
#include <iostream>
using namespace std;
#include <stack>
#include <string>
#include <cstdlib>
void init(string& s)
{
getline(cin,s);
s+="@";
}
bool is_optr(char c)
{
string optr_list("+-*/()@");
for(int i=0;i<optr_list.size();i++)
if(c==optr_list[i])
return true;
return false;
}
char first(char op1, char op2)
{
string tab[7];
tab[0]=">><<<>>";
tab[1]=">><<<>>";
tab[2]=">>>><>>";
tab[3]=">>>><>>";
tab[4]="<<<<<=E";
tab[5]=">>>>E>>";
tab[6]="<<<<<E=";
string optr_list("+-*/()@");
int op1_loc, op2_loc;
for(op1_loc=0;op1_loc<optr_list.size();op1_loc++)
if(optr_list[op1_loc]==op1)
break;
for(op2_loc=0;op2_loc<optr_list.size();op2_loc++)
if(optr_list[op2_loc]==op2)
break;
return tab[op1_loc][op2_loc];
}
double operate(double x, char op, double y)
{
switch(op) {
case '+':
return x+y;
break;
case '-':
return x-y;
break;
case '*':
return x*y;
break;
case '/':
return x/y;
break;
}
return -1;
}
double calc(string& s)
{
stack<char> optr;
optr.push('@');
stack<double> opnd;
char c=s[0];
s.erase(0,1);
while( c!='@' || optr.top()!='@' ) {
if( !is_optr(c) ) {
string num;
num.insert(num.begin(), c);
int loc=0;
while( !is_optr(s[loc]) )
loc++;
string num2(s,0,loc);
num+=num2;
s.erase(0,loc);
double x=atof(num.c_str());
opnd.push(x);
c=s[0];
s.erase(0,1);
}
else {
switch( first(optr.top(), c) ) {
case '<':
optr.push(c);
c=s[0];
s.erase(0,1);
break;
case '=':
optr.pop();
c=s[0];
s.erase(0,1);
break;
case '>':
char op;
op=optr.top();
optr.pop();
double a,b;
a=opnd.top();
opnd.pop();
b=opnd.top();
opnd.pop();
double res;
res=operate(b,op,a);
opnd.push(res);
break;
}
}
}
return opnd.top();
}
int main()
{
string exp;
double ans;
init(exp);
ans=calc(exp);
cout<<ans<<endl;
return 0;
}Top
8 楼docong（欢聚悲散一杯酒，南北东西万里程）回复于 2005-06-04 16:42:55 得分 0
foochow(恰似你的温柔) 兄台，你的态度太让我感动了，不过你的程序和我的要求相差1万8千里哦Top
9 楼docong（欢聚悲散一杯酒，南北东西万里程）回复于 2005-06-04 16:48:39 得分 0
foochow(恰似你的温柔) 兄台，你的第二个程序可否加点注释！！^_^Top
10 楼foochow（无聊,灌水......）回复于 2005-06-04 16:54:32 得分 0
这个是我收藏的,也没仔细看过,你自己看吧,嘿嘿Top
11 楼foochow（无聊,灌水......）回复于 2005-06-04 16:58:56 得分 0
殷人昆 数据结构(面向对象方法与C++描述),这本书上有,自己看看去写吧-_-Top
12 楼yyj1982（一切从头开始，好好学英语）回复于 2005-06-04 17:00:55 得分 0
学习中！！！Top
13 楼useresu（俗人)(灌水是我无言的抗议）回复于 2005-06-04 17:19:35 得分 0
温柔的程序好象是把中缀改成后缀的程序.
1的要求可以满足啊Top
14 楼docong（欢聚悲散一杯酒，南北东西万里程）回复于 2005-06-04 17:34:46 得分 0
1也有点问题
Top
15 楼zdy_8212（zdy_8212）回复于 2005-06-04 17:42:01 得分 0
1.抽取字母在没有碰到右括号时，所有的均以alpha[]入栈，下面的就是oalpha[]入栈。符号以反方向分析分别存入sing[]，osing[]。
2.分析整个式子，如果在符号的后方还有字母，设flag=1;压栈alpha[],当flag为真时，碰到第一个符号时就让缓冲的数组腾出空间存入左右括号，然后。。。。Top
16 楼foochow（无聊,灌水......）回复于 2005-06-04 17:48:21 得分 0
//先写个中缀变后缀的给你,别的晚上自习回来在写-_-
#include<iostream>
#include<string>
#include<stack>
#include<cctype>
using namespace std;
int isp(char optr)
{
switch (optr)
{
case '=': return 0;
case '(': return 1;
case '^': return 7;
case '*': return 5;
case '/': return 5;
case '%': return 5;
case '+': return 3;
case '-': return 3;
case ')': return 8;
default: return 0;
}
}
int icp(char optr)
{
switch(optr)
{
case '=': return 0;
case '(': return 8;
case '^': return 6;
case '*': return 4;
case '/': return 4;
case '%': return 4;
case '+': return 2;
case '-': return 2;
case ')': return 1;
default: return 0;
}
}
int main()
{
stack<char>s;
s.push('#');
char ch,y;
cout<<"请输入中缀表达式以'#'结束:";
while(cin.get(ch)&&ch!='#')
{
if(isdigit(ch)||isalpha(ch))cout<<ch;
else if(ch==')')
{
y=s.top();s.pop();
while(y!='(')
{
cout<<y;
y=s.top();s.pop();
}
}
else
{
y=s.top();s.pop();
while(isp(y)>icp(ch))
{
cout<<y;
y=s.top();s.pop();
}
s.push(y);s.push(ch);
}
}
while(!s.empty()){y=s.top();s.pop();cout<<y;}
system("PAUSE");
return 0;
}Top
17 楼o1n（小毛子）回复于 2005-06-04 18:10:59 得分 0
以前我做的是LL1语法分析。
帮你顶下吧。Top
18 楼mostideal（三甲）回复于 2005-06-04 18:13:46 得分 0
学习。。Top
19 楼WaterCold（飓风）回复于 2005-06-04 18:21:57 得分 0
可以考虑用二叉树
Top
20 楼visual4825（）回复于 2005-06-04 18:39:52 得分 0
利用堆栈, 读入表达式,
1.如果读入的字符是operand, 则放入堆栈中,
2.如果读入的是unary or binary operator, 则从堆栈中相应取出若干个operands, 进行运算,运算结
果再放入堆栈中.Top
21 楼docong（欢聚悲散一杯酒，南北东西万里程）回复于 2005-06-04 18:55:04 得分 0
WaterCold(飓风)纯粹在乱弹琴，要把表达式构造成二叉树就够你受的了！简直是……
你要学学人家温柔——多做事少说话！Top
22 楼docong（欢聚悲散一杯酒，南北东西万里程）回复于 2005-06-04 18:56:05 得分 0
第二个问题的关键是怎么给出加括号的算法Top
23 楼docong（欢聚悲散一杯酒，南北东西万里程）回复于 2005-06-04 19:00:16 得分 0
mccxj(爱逛街的老鼠)
我负责任的给你说，你的思路和我开始的思路是一样的——但是行不通！！^_^Top
24 楼mccxj（老鼠不逛街）回复于 2005-06-04 19:23:38 得分 0
呵呵。。是吗？我随便想了一下。。。。没试过。。Top
25 楼Heaven_Redsky（火骑士）回复于 2005-06-04 20:42:48 得分 0
对2的一点想法，还不成熟，没时间写代码实现，研究可行性了
可不可以把字符以栈的方法存入 当遇到第一个计算符的时候就暂停字符入栈
开始对计算符进行类似入队列的操作，即先进先出的顺序，直到遇到下一个字符为止。
然后开始对现有的字符和计算符进行出栈和出队列的匹配
当然，要把匹配后的表达式采用一定的办法当作一个字符进行再次入栈的操作，以完成进一步的匹配。当献出队列的计算符优先级低于后面的优先级的时候，加括号。
当计算符队列为空的时候，继续前面的字符入栈和计算符入队列的操作，直至结束。Top
26 楼foochow（无聊,灌水......）回复于 2005-06-04 21:03:22 得分 0
刚才上课回来写了下第2个,为了方便,我只用了+ - * / 4种运算,如果需要还可以添加乘方^,求模%运算,实现部分代码和乘除是一摸一样的,我这个方法有可能比较笨,不知道谁有更好的办法没.
Top
27 楼foochow（无聊,灌水......）回复于 2005-06-04 21:04:50 得分 0
//这个只能把后缀表达式转化为中缀表达式,如果要计算值,只要后面添加计算的代码就可以
#include<iostream>
#include<stack>
#include<string>
using namespace std;
int main()
{
stack<string>s;
char ch;
string temp1,temp2;
cout<<"请输入后缀表达式,以#结束:";
while(cin.get(ch)&&ch!='#')
{
string temp3("+"),temp4("-"),temp5("+"),temp6("/"),temp7("("),temp8(")"),temp9("*");
if(isdigit(ch)||isalpha(ch))
{
string temp(1,ch);s.push(temp);
}
else
{
switch(ch)
{
case '+':
temp1=s.top();s.pop();
temp2=s.top();s.pop();
temp2+=temp3;temp2+=temp1;s.push(temp2);
break;
case '-':
temp1=s.top();s.pop();
temp2=s.top();s.pop();
temp2+=temp4+=temp1;s.push(temp2);
break;
case '*':
temp1=s.top();s.pop();
temp2=s.top();s.pop();
if(temp2.size()!=1&&temp1.size()==1)
{
temp7+=temp2+=temp8+=temp9+=temp1;
s.push(temp7);
}
else if(temp2.size()==1&&temp1.size()!=1)
{
temp2+=temp9+=temp7+=temp1+=temp8;
s.push(temp2);
}
else if(temp2.size()==1&&temp1.size()==1)
{
temp2+=temp9+=temp1;
s.push(temp2);
}
else
{
string temp71=temp7,temp81=temp8;
temp71+=temp2+=temp81+=temp9+=temp7+=temp1+=temp8;
s.push(temp71);
}
break;
case '/':
temp1=s.top();s.pop();
temp2=s.top();s.pop();
if(temp2.size()!=1&&temp1.size()==1)
{
temp7+=temp2+=temp8+=temp6+=temp1;
s.push(temp7);
}
else if(temp2.size()==1&&temp1.size()!=1)
{
temp2+=temp6+=temp7+=temp1+=temp8;
s.push(temp2);
}
else if(temp2.size()==1&&temp1.size()==1)
{
temp2+=temp6+=temp1;
s.push(temp2);
}
else
{
string temp71=temp7,temp81=temp8;
temp71+=temp2+=temp81+=temp6+=temp7+=temp1+=temp8;
s.push(temp71);
}
default:break;
}
}
}
cout<<s.top()<<endl;
system("PAUSE");
return 0;
}Top
28 楼qhfu（改个名字）回复于 2005-06-04 22:05:58 得分 20
你这个问题最好是用二叉树做 ，Top
29 楼docong（欢聚悲散一杯酒，南北东西万里程）回复于 2005-06-05 13:13:11 得分 0
温柔真的很温柔^_^Top
30 楼cooljjyy（叽叽歪歪）回复于 2005-06-05 13:57:15 得分 0
我晕，第2种比第1种简单多了。书上都说了，计算机处理不了那么复杂的分析，所以才用后缀表达式。说明后缀表达式的分析比中缀表达式简单得多。看来你的大学计算机原理没学好。
计算的过程用栈的原理就可以了，只需要有两个处理：1.读到操作数直接入栈，2.读到运算符号从栈顶取出两个操作数(或者表达式)然后计算出表达式字符串，再压回栈中。
简单表示如下：
读取的元素 栈的内容(用','隔开)
a a
b b,a
c c,b,a
d d,c,b,a
－ (c-d),b,a
× b*(c-d),a
＋ (a+(b*(c-d)))
e e,(a+(b*(c-d)))
f f,e,(a+(b*(c-d)))
÷ (e÷f),(a+(b*(c-d)))
－ ((a+(b*(c-d)))-(e÷f))
原理非常简单，如果你懒的话可以每次计算表达式的时候加上括号()，这样出来的最终结果就不会错。否则你要根据运算符的优先级去判断是否需要加上括号()比较麻烦的。
Top
31 楼cooljjyy（叽叽歪歪）回复于 2005-06-05 14:03:35 得分 0
我想了一下，判断括号也不复杂，只要给每个表达式加上一个"运算符号"的属性即可，即使表达式很复杂，最终都可以理解为2个表达式的运算，运算符号只有一个。
每次读到新的运算符号取出两个表达式的时候，判断一下表达式的"运算符号"和当前的原算符号的优先级，如果当前运算符号的优先级低于任何一个表达式，那么需要加上括号。最后形成新的表达式时，就把当前运算符号设置为新表达式的"运算符号"。Top
32 楼djfu（飞龙在天）回复于 2005-06-05 14:37:39 得分 0
我晕，第2种比第1种简单多了。
----------------
第一种方法更简洁。Top
33 楼djfu（飞龙在天）回复于 2005-06-05 14:59:27 得分 0
我把我收藏的也贴出来。
#include <stdio.h>
#include <STDLIB.H>
#define M 20
typedef struct node{ char data;
struct node *lchild, *rchild;} BTnode;
BTnode *creat()
{
BTnode *t;
char ch;
scanf ("%c",&ch);
if (ch=='#')
t=NULL;
else
{
t=(BTnode *)malloc(sizeof(BTnode));
t->data=ch;
t->lchild=creat();
t->rchild=creat();
}
return t;
}
void inorder (BTnode *t)
{
int i = 0;
BTnode* s[M];
do {
while(t!=NULL)
{s[i++]=t;t=t->lchild;}
if (i>0)
{t=s[--i];
printf("%c",t->data);
t=t->rchild;
}
}while (i>0||t!=NULL);
}
void preorder(BTnode *t)
{int i=0;
BTnode *s[M];
do{while (t!=NULL)
{printf("%c",t->data);
if(t->rchild!=NULL)
s[i++]=t->rchild;
t=t->lchild;
}
if(i>0)
t=s[--i];
}while(i>0||t!=NULL);
}
void postorder(BTnode *t)
{
int s1[M];
int i=0;
BTnode *s[M];
do{
while (t!=NULL)
{s[i]=t;
s1[i++]=0;
t=t->lchild;
}
while (i>0&&s1[i-1]==1)
{
t=s[--i];
printf("%c",t->data);
free(t);
}
if (i>0)
{ s1[i-1]=1;
t=s[i-1];
t=t->rchild;
}
}while(i>0);
}
void main()
{ BTnode *t;
printf("input data:");
t=creat();
printf("Preorder:");
preorder(t);
printf("\nInorder:");
inorder(t);
printf("\nPostorder:");
postorder(t);
}Top
34 楼docong（欢聚悲散一杯酒，南北东西万里程）回复于 2005-06-05 15:12:27 得分 0
1、cooljjyy(叽叽歪歪) :关于你的道理我都懂；人家温柔务实多了，你看清楚了温柔的代码不正是你所说的算法么！关于你的“书上都说了，计算机处理不了那么复杂的分析，所以才用后缀表达式。说明后缀表达式的分析比中缀表达式简单得多。”我想你是理解错了，正式因为你所说的后序表达式的处理更简单是才导致了将它重新逆转成中序的更难（2又不是要你用后序处理一个字符串）；
2、cooljjyy(叽叽歪歪) :关于你说“看来你的大学计算机原理没学好。”我不予讨论，不过我想你即便要说我没学好，也该是说编译和数据结构吧！
3、Top
35 楼docong（欢聚悲散一杯酒，南北东西万里程）回复于 2005-06-05 15:14:57 得分 0
djfu(向左走？向右走？)
C风格的，而且要定义M ，使用不方便扩展也不好Top
36 楼docong（欢聚悲散一杯酒，南北东西万里程）回复于 2005-06-05 15:35:52 得分 0
更要命的是：djfu(向左走？向右走？) 你根本没读懂要求
你的程序随便找本数据结构的书一大堆：
输入：－＋A##*B##-C##D##/E##F##
输出：a＋b×(c－d)－e÷f和a b c d － × ＋ e f ÷ －
输入先序输出后序中序，但问题是你的这个先序输入要建立在”人脑“构造出表达式的二叉树基础上
我就且不说你的判断优先级功能了，用二叉树实习我也想过，不过真的太复杂了，我想光是按表达式的顺序输入，构造一个能中序出表达式的二叉树就太难了，不知那位仁兄做过这个工作啊？
Top
