|
|
cout.setf(ios::fixed); //以定点形式显示浮点数
cout.precision(4); //设置小数部分的4位有效数字
设序列X={x1,x2,x3......xm}和Y={y1,y2,y3,....yn}，要求最长公共子序列，可以按照下面方式递归计算，：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm即可得到X和Y的最长公共子序列，当xm不等于yn的时候，必须解决两个子问题即找出Xm-1和Y的最长公共子序列和Yn-1和X的最长工公共子序列，然后这两个里面较长者为X和Y的最长公共子序列！ 首先建立子问题的最优值递归关系。用C[i][j]表示Xi和Yj的最长公共子序列的长度。其中，Xi={x1,x2,x3......xi},Yj={y1,y2,y3,....yn}，当i=0或者j=0时空序列是Xi和Yj的最长公共子序列，故因此，C[i][j]=0，即有 代码如下： C[i][j]=0，（i=0,j=0) C[i][j]=c[i-1][j-1]+1,xi=yj C[i][j]=max(C[i][j-1],C[i-1][j]),i,j>0,xi不等于yj述
最长公共子串（Longest common substring, 简称LCS）问题指的是求出给定的一组 字符串的长度最大的共有的子字符串。 举例说明，以下三个字符串的LCS就是 cde： abcde cdef ccde
现在的情况是给你2个字符串，请找到他们的LCS
请注意：字符可以不相邻；
输入
输入第一行包含一个整数T，表示有T组数据；
对于每组数据包含2行，每行包含一个非空字符串，长度不超过1000个字符
输出
对于每组数据输出他们的LCS的长度，保证每组数据存在LCS；
样例输入
2 abcde cdef aaaaaaa aaabaaa
样例输出 3 6
分析：
设序列X={x1,x2,x3......xm}和Y={y1,y2,y3,....yn}，要求最长公共子序列，可以按照下面方式递归计算，：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm即可得到X和Y的最长公共子序列，当xm不等于yn的时候，必须解决两个子问题即找出Xm-1和Y的最长公共子序列和Yn-1和X的最长工公共子序列，然后这两个里面较长者为X和Y的最长公共子序列！ 首先建立子问题的最优值递归关系。用C[i][j]表示Xi和Yj的最长公共子序列的长度。其中，Xi={x1,x2,x3......xi},Yj={y1,y2,y3,....yn}，当i=0或者j=0时空序列是Xi和Yj的最长公共子序列，故因此，C[i][j]=0，即有 C[i][j]=0，（i=0,j=0)
C[i][j]=c[i-1][j-1]+1,xi=yj
C[i][j]=max(C[i][j-1],C[i-1][j]),i,j>0,xi不等于yj 实现代码如下： #include<stdio.h>
#include<string.h>
int c[1002][1002]={0};
int main()
{
int N,m,n,i,j;
char x[1002],y[1002];
scanf("%d",&N);
while(N--)
{
scanf("%s",x);
scanf("%s",y);
m=strlen(x);
n=strlen(y);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
if(x[i-1]==y[j-1])
{
c[i][j]=c[i-1][j-1]+1;
}
else if(c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];
}
else
{
c[i][j]=c[i][j-1];
}
}
printf("%d\n",c[m][n]);
}
return 0;
} 参考自： http://yangchuanhuahpu.blog.163.com/blog/static/18631884020125272205862/
转。
// %.*s 其中的.*表示显示的精度 对字符串输出(s)类型来说就是宽度
// 这个*代表的值由后面的参数列表中的整数型(int)值给出
// 例如：
printf("%.*s\n", 1, "abc"); // 输出a
printf("%.*s\n", 2, "abc"); // 输出ab
printf("%.*s\n", 3, "abc"); // 输出abc >3是一样的效果 因为输出类型type = s，遇到'\0'会结束
描述 对于一个字符串S1，其中S2是他的一个子串（长度严格小于S1长度），如果S2在S1中出现次数超过1次，那么S2就是一个重复子串，现在的要求是给定S1，请求出他的最长重复子串；
如果有多个长度一样的最长子串，请输入字典序最小那个串；
比如bbbaaaccc
那么最长子串就是aa
输入 第一行包含一个整数T，表示有T组数据
对于每组数据包含一行，该行有一个字符串，长度小于10,000
输出 对于每组数据请输出他的最长重复子串，保证每组数据都有；
样例输入 2 abacabac abacabbac
样例输出 abac bac
代码测试通过（普通版）：
#include<stdio.h> #include< string.h> #define N 10000 int main() { char a[N]; int i,j,n,t,p,max,t1; scanf("%d",&t1); while(t1--) { max = 0; scanf("%s",a); n=strlen(a); for(i=0;i<n;i++) { for(j=i+1;j<n;j++) { t=0; while(a[i+t]==a[j+t]&&(j+t)<n) t++; if(t>max) { max=t; p=i; } else if(t == max) //如果有长度一样的最长重复子串，那么比较它们的字典序
{ if(a[i]<a[p]) { max = t; p = i; } } } } for(i=p;i<p+max;i++) printf("%c",a[i]); printf("\n"); } return 0; } ²）。
第二种方法是用后缀数组实现。转自：http://hi.baidu.com/qwertlooker/item/44f3fe52ad772cdbd58bacfd
如果程序至多可以处理MAXN个字符，这些字符被存储在数组c中： #define MAXN 5000000
char c[MAXN], *a[MAXN]; 在读取输入时，首先初始化a,这样，每个元素就都指向输入字符串中的相应字符： while (ch = getchar()) != EOF
a[n] = &c[n];
c[n++] = ch;
c[n] = 0 //将数组c中的最后一个元素设为空字符，以终止所有字符串 这样，元素a[0]指向整个字符串，下一个元素指向以第二个字符开始的数组的后缀，等等。如若输入字符串为"banana",该数组将表示这些后缀：
a[0]:banana a[1]:anana a[2]:nana a[3]:ana a[4]:na a[5]:a 由于数组a中的指针分别指向字符串中的每个后缀，所以将数组a命名为"后缀数组"
第二，对后缀数组进行快速排序，以将后缀相近的（变位词）子串集中在一起 qsort(a, n, sizeof(char*), pstrcmp)后 a[0]:a a[1]:ana a[2]:anana a[3]:banana a[4]:na a[5]:nana
第三，使用以下comlen函数对数组进行扫描比较邻接元素，以找出最长重复的字符串： for i = [0, n)
if comlen(a[i], a[i+1]) > maxlen
maxlen = comlen(a[i], a[i+1])
maxi = i
printf("%.*s\n", maxlen, a[maxi]) 由于少了内层循环，只是多了一次排序，因此该算法的运行时间为O(n logn). （nlogn比n大，取nlogn） 实现代码如下： #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXCHAR 10000 //最长处理10000个字符
char c[MAXCHAR], *a[MAXCHAR];
int comlen( char *p, char *q ){ //计算最长重复子串的长度
int i = 0;
while( *p && (*p++ == *q++) )
++i;
return i;
}
int pstrcmp( const void *p1, const void *p2 ){
return strcmp( *(char* const *)p1, *(char* const*)p2 );
}
int main( ){
int t;
char ch;
int i, temp;
scanf("%d\n",&t);
while(t--)
{
int n=0;
int maxlen=0, maxi=0;
while( (ch=getchar())!='\n' ){
a[n]=&c[n];
c[n++]=ch;
}
c[n]='\0';
qsort( a, n, sizeof(char*), pstrcmp ); //快速排序对后缀数组进行排序，以使后缀相同的子串集中在一起，
//以便接下来comlen函数对这些子串进行计算其最长重复子串
for(i=0; i<n-1; ++i ){
temp=comlen( a[i], a[i+1] );
if( temp>maxlen )
{
maxlen=temp;
maxi=i;
}
}
printf("%.*s\n",maxlen, a[maxi]); //输出最长重复子串
}
return 0;
}
第三种方法似乎可以用后缀树实现，效率可以提高到O(n)，具体的后缀树讲解可以参照这篇文章：
http://blog.csdn.net/v_july_v/article/details/6897097（PS:智商有限，后面部分讲解理解不了）
归并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 例如，有数列{6，202，100，301，38，8，1} 1. 刚开始的分组如下： i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 比较次数为3次 2. 第二次，两两分组合并 i=2 [ 6 100 202 301 ] [ 1 8 38 ] 比较次数为4 3. 第三次，继续合并 i=3 [ 1 6 8 38 100 202 301 ] 比较次数为4 总计的比较次数为11次 归并排序具体工作原理如下（假设序列共有n个元素）： 1. 将序列每相邻两个数字进行归并操作，形成floor(n / 2)个序列，排序后每个序列包含两个元素 2. 将上述序列再次归并，形成floor(n / 4)个序列，每个序列包含四个元素 3. 重复步骤2，直到所有元素排序完毕 归并操作的过程如下： 1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置 3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 4. 重复步骤3直到某一指针达到序列尾 5. 将另一序列剩下的所有元素直接复制到合并序列尾 自底向上归并，如图所示：  递归实现代码： #include <iostream>
using namespace std;
void merge(int*arr, int p, int q, int r)
{
int n1 = q - p + 1;
int n2 = r - q;
int* L = new int[n1];
int* R = new int[n2];
for(int i = 0; i < n1; i++)
{
L[i] = arr[p + i];
}
for(int j = 0; j < n2; j++)
{
R[j] = arr[q + j + 1];
}
int i = 0;
int j = 0;
int k = p;
while((i < n1) && (j < n2))
{
if(L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
if (i < n1)
{
for(; i < n1; i++, k++)
{
arr[k] = L[i];
}
}
if (j < n2)
{
for(; j < n2; j++, k++)
{
arr[k] = R[j];
}
}
}
void mergesort(int* arr, int p, int r)
{
int q = 0;
if(p < r)
{
q = (p + r) / 2;
mergesort(arr, p, q);
mergesort(arr, q + 1, r);
merge(arr, p, q, r);
}
}
int main()
{
int a[] = {5, 2, 4, 7, 1, 3, 2, 6};
mergesort(a, 0, 7);
for(int i = 0; i < 8; i++)
{
cout << a[i] << " ";
}
cout << endl;
return 0;
} 非递归代码实现： /**
* merge_sort: 非递归实现 --迭代
* 非递归思想: 将数组中的相邻元素两两配对。用merge函数将他们排序，
* 构成n/2组长度为2的排序好的子数组段，然后再将他们排序成长度为4的子数组段，
* 如此继续下去，直至整个数组排好序。
**/ #include <stdio.h> #include <stdlib.h> // merge_sort(): 非递归实现-自底向上
// 将原数组划分为left[min max] 和 right[minmax]两部分
void merge_sort( int *list, int length) { int i, left_min, left_max, right_min, right_max, next; int *tmp = ( int*)malloc( sizeof( int) * length); if (tmp == NULL) { fputs("Error: out of memory\n", stderr); abort(); } for (i = 1; i < length; i *= 2) // i为步长，1,2,4,8……
{ for (left_min = 0; left_min < length - i; left_min = right_max) { right_min = left_max = left_min + i; //right_min取left_max的值，以下要用到left_max的值才不会改变left_max原先值
right_max = left_max + i; if (right_max > length) //如果right_max超出了数组长度，则right_max等于数组长度
right_max = length; next = 0; while (left_min < left_max && right_min < right_max) //tmp[next]存储子数组中的最小值
tmp[next++] = list[left_min] > list[right_min] ? list[right_min++] : list[left_min++]; while (left_min < left_max) //如果left_min小于left_max，则将最小值原封不动地赋给list[--right_min]，right_min 要先减1
list[--right_min] = list[--left_max]; while (next > 0) //将tmp[next]存储的最小值放入list[--right_min]中
list[--right_min] = tmp[--next]; } if(i == 1) //打印第一次归并后的数字排列
{ for( int j=0;j<length;j++) printf("%d ",list[j]); printf("\n"); } } free(tmp); } int main() { int a[1000],t,i; scanf("%d",&t); for(i=0;i<t;i++) { scanf("%d",&a[i]); } merge_sort(a, t); // print array
for (i = 0; i < t; i++) printf("%d ", a[i]); return 0; }
动态规划解决01背包问题！ 代码
#include<stdio.h> int c[10][100];/*对应每种情况的最大价值*/int w[10],p[10];int knapsack(int m,int n){ int i,j,x[10]; //w为物品重量，p为价值
for(i=1;i<n+1;i++) scanf("\n%d%d",&w[i],&p[i]); for(i=0;i<10;i++) for(j=0;j<100;j++) c[i][j]=0;/*初始化数组*/ for(i=1;i<n+1;i++) for(j=1;j<m+1;j++) { if(w[i]<=j) /*如果当前物品的重量小于背包所能承载的重量*/ { if(p[i]+c[i-1][j-w[i]]>c[i-1][j]) /*如果本物品的价值加上背包剩下的空间能放的物品的价值*/ /*大于上一次选择的最佳方案则更新c[i][j]*/ c[i][j]=p[i]+c[i-1][j-w[i]]; else c[i][j]=c[i-1][j]; } else c[i][j]=c[i-1][j]; } printf("\n"); int contain = m; for(int i=n;i>0;--i) { if(c[i][contain] == c[i-1][contain])//未放入第i个物品，contain表示当前背包的承受重量
x[i-1] = 0; //考虑：f[i][j] = max{ f[i-1][j] 和 f[i-1][j - w[i]] + v[i] }, if ( f[i][j] == f[i-1][j] )
else //则说明物品i未放入；否则物品i 放入了背包中，最大承重量也相应减去w[i]
{ x[i-1] = 1; contain -= w[i]; // 放上了第i个物品，当前背包的重量要减去相应的物品i的重量，回溯
} } for(i=0;i<n;i++) { printf("%d ",x[i]); //1表示放入，0表示未放入
} printf("\n"); return(c[n][m]);}int main() { int m,n,i,j; scanf("%d %d",&m,&n); printf("Input the weight and value:\n"); printf("%d\n",knapsack(m,n)); return 0;}//测试数据：5 4
//2 12
//1 10
//3 20
//2 15
//结果：1 1 0 1 最大价值：37
给定一颗二叉树的逻辑结构如下图，（先序遍历的结果，空树用字符‘0’表示，例如AB0C00D00），建立该二叉树的二叉链式存储结构。
编写程序输出该树的所有叶子结点和它们的父亲结点
Input
第一行输入一个整数t，表示有t个二叉树
第二行起，按照题目表示的输入方法，输入每个二叉树的先序遍历，连续输入t行
Output
第一行按先序遍历，输出第1个示例的叶子节点
第二行输出第1个示例中与叶子相对应的父亲节点
以此类推输出其它示例的结果
Sample Input
3 AB0C00D00 AB00C00 ABCD0000EF000 Sample Output
C D B A B C A A D F C E
代码：
#include <iostream>
using namespace std;
class BiTreeNode
{
private:
BiTreeNode *leftChild; //左子树指针
BiTreeNode *rightChild; //右子树指针
public:
char data; //数据域
char father;
//构造函数和析构函数
BiTreeNode():leftChild(NULL), rightChild(NULL){}
BiTreeNode(char item, char father, BiTreeNode *left = NULL,
BiTreeNode *right = NULL):
data(item), father(father), leftChild(left), rightChild(right){}
~BiTreeNode(){}
BiTreeNode * &Left(void) //注意返回值类型为指针的引用类型
{return leftChild;}
BiTreeNode * &Right(void) //注意返回值类型为指针的引用类型
{return rightChild;}
};
class BiTree
{
private:
BiTreeNode *root; //根结点指针
int i;
void Destroy(BiTreeNode * &t);
void PreLeave(BiTreeNode * &t);
void Prefather(BiTreeNode * &t);
void CreateBiTree(BiTreeNode * &T,const char strTree[],char father);
public:
//构造函数和析构函数
BiTree(void):root(NULL),i(0){}; //构造函数
~BiTree(void){}; //析构函数
//构造二叉树
void MakeTree(const char item,char father, BiTree &left, BiTree &right); //构造二叉树
void MakeTree(const char strTree[]); //构造二叉树，利用先序遍历结果建树
void Destroy(void); //销毁二叉树
void PreLeave(); //前序遍历
void Prefather();
};
//2、定义销毁函数
void BiTree ::Destroy(void) //销毁二叉树，公有函数
{
Destroy(root);
}
void BiTree ::Destroy(BiTreeNode * &t)
//销毁二叉树，私有函数供共有函数调用
{
if(t != NULL && t->Left() != NULL)
Destroy(t->Left());
if(t != NULL && t->Right() != NULL)
Destroy(t->Right());
if(t != NULL)
{
// cout << t->data << " "; //此语句只是为了方便测试
delete t;
}
}
//3、定义建树函数
void BiTree::MakeTree(const char item, char father,BiTree &left, BiTree &right)
//构造数据域为item，左子树为left，右子树为right的二叉树
{
root = new BiTreeNode(item,father, left.root, right.root);
}
void BiTree::MakeTree(const char strTree[])
//构造二叉树，利用先序遍历结果建树，公有函数
{
i=0;
char rootfather = '0';
CreateBiTree(root,strTree,rootfather);
}
void BiTree::CreateBiTree(BiTreeNode * &T, const char strTree[],char father) //递归建树私有函数
{
char ch;
ch=strTree[i++];
if (ch=='0') T = NULL;
else
{
T=new BiTreeNode();
T->data = ch; // 生成根结点
T->father = father;
father = ch;
CreateBiTree(T->Left(), strTree,father); // 构造左子树
CreateBiTree(T->Right(), strTree,father); // 构造右子树
}
}
//4、定义先序遍历函数
void BiTree::PreLeave()
//前序遍历访问二叉树，公有函数
{
PreLeave(root);
}
void BiTree::PreLeave(BiTreeNode* &t)
//前序遍历访问二叉树，私有函数t
{
if(t)//若二叉树结点不为空，执行如下操作：
{
if(!t->Left() && !t->Right()) //如果当前结点是叶子
cout<<t->data<<" ";
PreLeave(t->Left());//2、先序遍历该结点的左孩子
PreLeave(t->Right());//3、先序遍历该结点的右孩子
}
}
//5、定义遍历父节点函数
void BiTree::Prefather()
{
Prefather(root);
}
void BiTree:: Prefather(BiTreeNode* &t)
//中序遍历访问二叉树，私有函数t
{
if(t)//若二叉树结点不为空，执行如下操作：
{
if(!t->Left() && !t->Right())//如果当前结点是叶子，输出它的父亲
cout<<t->father<<" ";
Prefather(t->Left());
Prefather(t->Right());
}
}
int main(void)
{
int n,i;
char strTree[800];
BiTree myTree;
cin>>n;
cin.get();
for(i=0;i<n;i++)
{
cin>>strTree;
myTree.MakeTree(strTree);
myTree.PreLeave();
cout<<endl;
myTree.Prefather();
cout<<endl;
myTree.Destroy();
}
return 0;
}
二叉树可以采用数组的方法进行存储，把数组中的数据依次自上而下,自左至右存储到二叉树结点中，一般二叉树与完全二叉树对比，比完全二叉树缺少的结点就在数组中用0来表示
结点存储的数据均为非负整数
Input
第一行输入一个整数t，表示有t个二叉树
第二行起，每行输入一个数组，先输入数组长度，再输入数组内数据，每个数据之间用空格隔开，输入的数据都是非负整数
连续输入t行
Output
每行输出一个示例的先序遍历结果，每个结点之间用空格隔开
Sample Input
3 3 1 2 3 5 1 2 3 0 4 13 1 2 3 4 0 5 6 7 8 0 0 9 10 Sample Output
1 2 3 1 2 4 3 1 2 4 7 8 3 5 9 10 6
分析：这道题的关键在于：设定数组位置从1开始编号，那么位置为i的结点，它的左孩子在数组的位置是2i，右孩子在数组的位置是2i+1
这道题的难点在把树建立起来，其他都容易。
代码：
#include <iostream>
using namespace std;
class BiTreeNode
{
private:
BiTreeNode *leftChild; //左子树指针
BiTreeNode *rightChild; //右子树指针
public:
int data; //数据域
//构造函数和析构函数
BiTreeNode():leftChild(NULL), rightChild(NULL){}
BiTreeNode(int item, BiTreeNode *left = NULL,
BiTreeNode *right = NULL):
data(item), leftChild(left), rightChild(right){}
~BiTreeNode(){}
BiTreeNode * &Left(void) //注意返回值类型为指针的引用类型
{return leftChild;}
BiTreeNode * &Right(void) //注意返回值类型为指针的引用类型
{return rightChild;}
};
class BiTree
{
private:
BiTreeNode *root; //根结点指针
int i,len; //len是树结点的数量
void Destroy(BiTreeNode * &t);
void PreOrder(BiTreeNode * &t);
void CreateBiTree(BiTreeNode * &T,const int arrTree[],int pos);
public:
//构造函数和析构函数
BiTree(void):root(NULL),i(0){}; //构造函数
~BiTree(void){}; //析构函数
//构造二叉树
void MakeTree(const int arrTree[],int num); //构造二叉树，利用先序遍历结果建树
void Destroy(void); //销毁二叉树
void PreOrder(); //前序遍历
};
//2、定义销毁函数
void BiTree ::Destroy(void) //销毁二叉树，公有函数
{
Destroy(root);
}
void BiTree ::Destroy(BiTreeNode * &t)
//销毁二叉树，私有函数供共有函数调用
{
if(t != NULL && t->Left() != NULL)
Destroy(t->Left());
if(t != NULL && t->Right() != NULL)
Destroy(t->Right());
if(t != NULL)
{
delete t;
}
}
//3、定义建树函数
void BiTree::MakeTree(const int arrTree[],int num)
//构造二叉树，利用先序遍历结果建树，公有函数
{
i=0;
len = num;
CreateBiTree(root,arrTree,1);//数组位置从1开始
}
void BiTree::CreateBiTree(BiTreeNode * &T, const int arrTree[],int pos) //递归建树私有函数
{
int ch;
ch=arrTree[pos];
if (ch == 0 || pos > len) T = NULL;
else
{
T=new BiTreeNode();
T->data = ch; // 生成根结点
i++;
if(i>len) return;
CreateBiTree(T->Left(), arrTree,2*pos); // 构造左子树
CreateBiTree(T->Right(), arrTree,2*pos+1); // 构造右子树
}
}
//4、定义先序遍历函数
void BiTree::PreOrder()
//前序遍历访问二叉树，公有函数
{
PreOrder(root);
}
void BiTree::PreOrder(BiTreeNode* &t)
//前序遍历访问二叉树，私有函数t
{
if(t!=NULL)//若二叉树结点不为空，执行如下操作：
{
cout<<t->data<<" ";//1、输出当前结点的数据，表示该结点被访问了
PreOrder(t->Left());//2、先序遍历该结点的左孩子
PreOrder(t->Right());//3、先序遍历该结点的右孩子
}
}
int main()
{
int m,i,j,k;
int *arrTree;
BiTree myTree;
cin>>m;
for(i=0;i<m;i++)
{
arrTree = new int[800];
cin>>k;
for(j=1;j<=k;j++)
cin>>arrTree[j];
myTree.MakeTree(arrTree,k);
myTree.PreOrder();
cout<<endl;
delete []arrTree;
myTree.Destroy();
}
return 0;
}
描述 给一些包含加减号和小括号的表达式，求出该表达式的值。表达式中的数值均为绝对值小于 10 的整数。
输入 第一行为表达式的个数 n，以下 n 行每行有一个表达式。每个表达式的长度不超过 20 个字符。
输出 对每个表达式，输出它的值。
样例输入 3 3-(2+3) -9+8+(2+3)-(-1+4) 0-0 样例输出 -2 1 0
//对每种情况都要考虑清楚
#include <cctype>
#include <iostream>
#include <string>
#include <stack>
#include <map>
using namespace std;
int getPrecedence(const char optr) //给各个操作符定义优先级顺序，利用map容器
{
map<char, int> precedTable;
precedTable['#'] = 0;
precedTable[')'] = 1;
precedTable['+'] = 2;
precedTable['-'] = 2;
precedTable['*'] = 3;
precedTable['/'] = 3;
precedTable['('] = 10;
return precedTable[optr];
}
int calculate(int a, char optr, int b)
{
switch (optr) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
default: return 0;
}
}
int evaluate(const string& expr)
{
stack<int> opnd;
stack<char> optr;
char last_ch = '\0'; //每次检查字符时的前一个字符
for (size_t i = 0; i != expr.size(); ++i) {
const char ch = expr[i];
if (isspace(ch)) { //如果是空格，即跳过
continue;
} else if (isdigit(ch)) { //如果是数字，则压入操作数栈
opnd.push(ch - '0');
} else {
if ((ch == '-' || ch == '+') && (last_ch == '\0' || last_ch == '(')) //遇到 '+'、'-'，则压入0进操作数栈
opnd.push(0); //如 7-1，遇'-'则压入0进栈，，'-'则进操作符栈，遇到下一个数1，计算0-1得-1
if (optr.empty() || ch == '(' || (optr.top() == '(' && ch != ')') || getPrecedence(ch) > getPrecedence(optr.top())) {
optr.push(ch);
}
else
{
while (!optr.empty() && optr.top() != '(' && getPrecedence(ch) <= getPrecedence(optr.top()))
{
int b = opnd.top(); opnd.pop();
int a = opnd.top(); opnd.pop();
opnd.push(calculate(a, optr.top(), b));
optr.pop();
}
if (ch == ')')
optr.pop();
else
optr.push(ch);
}
}
last_ch = ch;
}
while (!optr.empty()) {
int b = opnd.top(); opnd.pop();
int a = opnd.top(); opnd.pop();
opnd.push(calculate(a, optr.top(), b));
optr.pop();
}
int result = opnd.top(); opnd.pop();
return result;
}
int main()
{
int n;
cin >> n;
while (n-- > 0) {
string expr;
cin>>expr;
cout << evaluate(expr) << endl;
}
return 0;
}
#include<iostream>
#include<string>
using namespace std;
char a[100];
int i;
int eval()
{
int x=0;
while(a[i] == ' ') i++;
if(a[i] == '+')
{
i++;
return eval()+eval();
}
if(a[i] == '*')
{
i++;
return eval()*eval();
}
while((a[i] >= '0')&&(a[i]<= '9'))
x = 10*x +a[i++]-'0';
return x;
}
int main()
{
gets(a);
cout<< eval()<<endl;
return 0;
}
|